Definitions - Graph Theory Flashcards
Vertices
Dots in graph
Graph
Set of vertices and edges that end on a vertex
Edges
Connecting lines in graph
Adjacent vertices
Vertices that share common edge
Degree
Number of edges joining vertex
Size
Number of vertices
Connected graph
There is a way to get from one vertex to another
Loop
Start/finish at same vertex
Multiple edges
Vertices have multiple connecting edges
Simple graph
No multiple edges or loops
Regular graph
All vertices have same degree
Tree
Graph is connected. No circuits
Isomorphic graphs
First graph can be reconstructed by moving vertices of second graph
Walk
Sequence of edges and vertices
Closed walk
End of walk vertex is the same as starting vertex
Path
No edge travelled more than once
Chain
No vertex visited more than once
Closed path/circuit/cycle
Path that starts/ends on same vertex
Girth
Length of shortest circuit
Hamiltonian circuit
Circuit that starts at vertex, passes through all vertices once and returns to dip starting vertex
Eulerian path
Path that contains every edge once
Eulerian circuit
Eulerian path that starts/ends on same vertex
