d1 vocab Flashcards
1
Q
eulerian graphs
A
all verticies are even. semi eulerian have exactly 2 odd vertices
2
Q
a walk
A
route through the graph along edges from one vertix to the next
3
Q
a path
A
a walk in which no vertex is visited more than once
4
Q
a trail
A
a walk in which no edge is visited more than once
5
Q
a cycle
A
a walk in which start and end vertex is the same and no other vertex is visited more than once
6
Q
a hamiltonian cycle
A
a cycle than includes every vertex
7
Q
handshaking lemma
A
in any undirected graph, the sum of the degrees of the vertices is equal to twice the number of edges (as a consequence, number of odd nodes must be even)
8
Q
tree
A
connected graph with no cycles
9
Q
spanning tree
A
a subgraph which includes all vertices of original graph and is also a tree
