Graph Theory

Question 1

Sequence of vertices that follows edges

Answer 1

Walk

Question 2

Walk that does not repeat edges

Answer 2

Trail

Question 3

Sequence of vertices that does not repeat edges

Answer 3

Trail

Question 4

Trail that doesn’t repeat vertices

Answer 4

Path

Question 5

Sequence of vertices that repeats neither edges nor vertices

Answer 5

Path

Question 6

Sequence of vertices that starts and ends at the same place

Answer 6

Closed Walk

Question 7

Sequence of vertices that starts and ends at the same place and doesn’t repeat edges

Answer 7

Tour

Question 8

Closed trail

Answer 8

Tour

Question 9

Tour that has positive length and doesn’t repeat vertices

Answer 9

Cycle

Question 10

Sequence of vertices that starts and ends at the same place and doesn’t repeat edges or vertices

Answer 10

Cycle

Question 11

A tour is Eulerian when

Answer 11

it uses every edge once and visits every vertex

Question 12

A trail, walk, or path is semi Eulerian when

Answer 12

it uses every edge once and visits every vertex

Question 13

A graph is Eulerian iff

Answer 13

it has an euler tour

Question 14

A graph is semi-Eulerian iff

Answer 14

it has an euler trail, walk, or path

Question 15

Handshake lemma for nondirectional graph

Answer 15

sum of degrees = 2 times number of edges

Question 16

Handshake lemma for directional graph

Answer 16

sum of degree of vectors in = number of edges = sum of degree of vectors out

Question 17

u can reach v or v is reachable from u

Answer 17

u-v walk

Question 18

every pair of vertices is strongly connected

Answer 18

graph G is strongly connected

Question 19

strongly connected graph and every vertex has in degree = out degree

Answer 19

directed graph has an euler tour

Question 20

induced subgraph on the set of strongly connected vertices with v

Answer 20

strongly connected component of v = [v]

Question 21

All strongly connected components are treated as one vertex and removing all self loops

Answer 21

condensation graph = DAG

Question 22

Directed Acyclic Graph

Answer 22

digraph with no cycles

Question 23

edge that is only path between endpoints

Answer 23

covering edge

Question 24

you take a DAG and remove all edges except covering edges

Answer 24

Hasse Diagram

Question 25

u, v comparable when

Answer 25

u can reach v or v can reach u

Question 26

subset of vertices where every pair comparable

Answer 26

chain

Question 27

maximum size chain

Answer 27

critical path = set of vertices

Question 28

subset of vertices in which every element is incomparable

Answer 28

antichain

Question 29

depth(v)

Answer 29

length of longest path that ends at v