Graph theory Flashcards
Complete graph
Everyone is directly connected to everyone (triangle, star, etc)
Simple graph
No loop, or many edges
Adjacency matrix
How many connections between 2 vertices there are ( from is row to is column)
Strongly connected graph
Can get to every vertex from any vertex IN ANY DIRECTION
Connected graph
Can get to every vertex from any vertex
Sum in row in an adjacency matrix
In degree
Sum in column of an adjacency matrix
Out degree
Walk
Sequence of vertices visitied
Length of a walk
How many edges you visited
How do you see how many ways there are to have a walk of length n from A to B
You raise the adjacency matrix to the power of that n
How do you find a number of walks length n and less
M^1 + M^2+M^3…+M^n
Trail
No edge is repeated
Eulerian trail
Every edge is visited exactly once
Circuit
Trail that ends at its beginning point
Eulerian circuit
Trail that ends at its beginning point and visits every edge exactly once
What order are odd degree vertices in an Eulerian circuit
Start and finish points
Semi - Eulerian
Has one pair of odd vertices
What does Chinese postman want to achieve
Least weight, every edge once, cycle
How to solve Chinese Postman
All even : Sum of all weights
One pair odd: their own connection and sum of all weights
More than one pair odd: Their minimum pairing plus sum of all weights
Process of odd pairings CP?
Find the pair of odds that has the least weight, draw dotted lines that can be repeated.
Tree
Connected graph with no cycles
Kruskal’s Algorithm
1) Find edge with least weigth
2) Add the edge of least weight next to it that hasnt been selected yet and not in a cycle
3) Keep going till done
Primm’s Algorithm
1) Select any vertex
2) Add the edge of least weight next to it (not in a cycle!)
3) Repeat
Path
No vertex shall be repeated
