Terminology Flashcards
Vertex
Points in a graph
Edge
Connects two vertices together
Degree
Number of lines that go into a vertex
Connected
A graph where you can go from vertex to any other vertex
Loop
Starts at a vertex and ends at the same vertex
Multiple edges
More than one edge going from vertex to another
Simple graph
Graph with no multiple edges or loops
Regular graph
Every vertex has same edges
Degree equal at every vertex
Tree
Connected with no circuit
Isomorphic graph
Two graphs that look different but are identical - Move points around.
How to check if a graph is isomorphic
Check if the degrees match
Walk
Go from one point to another
Path
Walk but can’t travel on edge twice
Chain
Path in which you can’t move over vertex and edge twice
Closed path/Circuit
Starts and ends at same point
Hamiltonian circuit
Travels every single vertex and ends at the same point
Eulerian path
Path that goes through every edge once
Eluerian circuit
Eulerian path that starts and ends at the same point
How to figure out if a graph is a Eulerian path
Work out degree
More than two odd vertices - Impossible
If two - Start at one odd end and end at the other
How to find a Eulerian circuit
All vertices must have an even number of degrees.
