Graph Thoery Flashcards
Connected graph
All vertices directly or indirectly connected
Simple graph
no loops or multiple edges
tree
connected graph with no circuits
undirected graph
Weight of A-B = B-A. If loop/multiple edge is present graph is directed
weight of an edge
any factor ascribed to the edge
order
number of vertices in the graph
degree of a vertex
number of edges leading to/from that vertex
Regular graph
all vertices of same degree
circuit
a path that starts and ends at same vertex
path
route between 2 specified vertices so that no edge used more than once, not all edges need to be used. starting point not usually endpoint.
size
total number of edges
Adjacent vertices
directly connected by a common edge
Neighborhood of a vertex
vertices that are connected to a vertex
girth
sum of weight of edges
planar graph
drawn without touching
formula for degree of regular graph
degree = order-1
formula for size of complete graph
1/2*order(order-1)
Isomorphic graphs
Same size, order + neighborhood. Test to see how many hops it takes to get back to a starting vertex.
Eulerian path
every edge once, starts and ends at different vertices, vertices can be visited more than once. Must begin and end at the pair of odd vertices. Only exists if there is 1 pair of vertices of odd degree
Eulerian circuit
every edge once, starts and ends at same vertex, vertices may be visited more than once. Only exists if no vertices of odd degree
Hamiltonian circuit
each vertex once before returning to starting vertex, doesn’t need to use every edge.
circuit
a path that starts and ends at same vertex
