Graph Theory Flashcards
Nodes/vertices
Vertexes or dots on the graph
Edge/arc
Line connecting two vertices
Multiple edges
Two routes to travel between the same two nodes
Loop- give an example
An edge that takes you back to the same node- for example, a button on a home page that takes you back on to the homepage.
Simple graph
A graph with no loops or multiple arcs
Isomorphic graphs
Graphs that represent the same rhing
Complete graph
Every vertex is directly connected to every other vertex
Complete graph notation
Kn, where n is the number of nodes
Complete graph edges sequence..
Triangular numbers
Formula for the total number edges in a complete graph
1/2 n (n-1)
Bipartite graph
A graph is bipartite if it can be broken down into two sets of vertices, and the vertices cannot be directly connected to each other.
Common use of bipartite graphs
Allows you to allocate workers to specific jobs
Complete bipartite graph
Kr, s where set on the LHS has ‘r’ nodes/vertices and the RHS has ‘s’ nodes/vertices
Order/degree of a vertex
How many edges are coming out of a vertex, a loop counts as two orders
- even orders and odd orders
Semi-Eularian
Two odd order vertices
- start at one odd vertices and end at the next one
