Graph Theory

Question 1

What is an edge?

Answer 1

Lines

Question 2

What is vertices/nodes?

Answer 2

Dots

Question 3

What is a Loop?

Answer 3

An edge that joins a vertex to itself

Question 4

Pendant

Answer 4

Degree 1 vertex

Question 5

What is a Walk?

Answer 5

A sequence of vertices and edges
where BOTH CAN be repeated

Question 6

What is a Path?

Answer 6

A sequence of vertices and edges
where BOTH CANNOT be repeated

Question 7

What is a Trail?

Answer 7

A walk
where EDGE CANNOT be repeated

Question 8

What is a Circuit?

Answer 8

A closed trail

Question 9

What is a Cycle?

Answer 9

A closed path

Question 10

What is an Eulerian Path?

Answer 10

A path that uses EACH EDGE EXACTLY once

*graph is traversable only if this path exists

Question 11

How to check for Eulerian Path?

Answer 11

The graph has 0 or 2 vertices of odd degree.

Question 12

What is an Eulerian Circuit?

Answer 12

Graph contains CLOSED Eulerian Path

Question 13

How to check for Eulerian Circuit?

Answer 13

All vertices to have EVEN degree

Question 14

What is a Hamiltonian Path?

Answer 14

A path that visits EACH VERTEX EXACTLY once

also known as traceable path

Question 15

What is a Hamiltonian Cycle?

Answer 15

A closed Hamiltonian Path

Question 16

What is Dijkstra’s Algorithm used for?

Answer 16

Find shortest distance from vertex ‘a’ to every other vertex