Graph Theory Flashcards
Simple Graph Definition
A graph with no loops of multiple edges.
Complete Graph Defintion
A graph where every vertex is connected to every other vertex.
How many edges does a complete graph of Kn nodes have?
1/2n(n-1)
Bipartite Graphs
- A graph where the nodes are in two distinct sets
- Every edge connects a member of the first set to a member of the second set
- Vertices cannot be connected to nodes in the same set.
Connected Graph
A graph in which it is possible to go from any vertex to any other vertex (even if you have to travel through other vertices).
Degree/Order Of A Vertex
How many ends of edges there are at the vertex (how many lines go in/out of the vertex).
What does an odd total order look like?
It is not possible to draw a graph with an odd total order.
Kn Meaning
This represents a complete graph with n vertices.
How many arcs in Kn
n (n-1) / 2
Digraph Defintion
- A diagraph (directed graph) is one in which at least one edge has a direction associated with it.
- Normally has a source (original node in which all preceding arcs come from).
- Normally has an end node, called the sink, which all arcs eventually reach.
Kr,s Meaning
This represents a complete bipartite graph, where r is the number of nodes on the left, and s on the right.
Tree Defintion
A simply connected graph with the minimum number of arcs is called a tree, and with no cycles e.g triangle/square.
Network
A graph that has weights attached.
Minimum Spanning Tree
A tree that joins all vertices in a graph (as a tree) in the cheapest possible way.
Eularian Graph
- It is possible to make a trail that uses all edges once, starting and ending at the same vertex.
- Has no nodes with odd degree.
Semi-Eularian Graph
- It is possible to make a trail that uses all the edges once, starting and ending at different vertices.
- Have exactly two odd nodes, possible to make a trail if you start at one odd vertex and finish at the other.
Trail Definition
A trail is a sequence of joined up edges such that no edge comes one after another, e.g. AEBCED.
Path Definition
A path is a sequence of edges such that the end vertex on one edge is the start of the next, and in which no vertex is visited more than once (except that the first and the last may be the same), e.g. ABECD
Cycle Defintion
A cycle is a closed path, e.g. ABEA
A simply connected graph, G, has 8 vertices. What is the minimum/maximum number of edges that G could have?
Min = n - 1 = 7
Max = (n x (n-1)) / 2
8 x 7 / 2 = 56/2 = 28
What is a greedy algorithm?
A greedy algorithm is an algorithm that finds a solution to problems in the shortest time possible.
Outline how Kruskal’s Algorithm works (Minimum Spanning Tree)
1) Select the shortest edge in a network
2) Select the next shortest edge
3) Repeat this process until all vertices are connected.
4) Make sure you do not create a cycle at any point, or it is not a tree.
Outline how Prim’s Algorithm works (Minimum Spanning Tree)
1) From the starting vertex, select the shortest edge connected to that vertex.
2) Selected the shortest edge connected to all vertices already connected.
3) Repeat until all vertices are connected.
Dijkstra’s Algorithm
- Start with first node, make number = 1, final value = 0
- Add the running value in all connected nodes.
- Then take the node with the smallest running value, then we know that’s the final value.
- From that node see what you can go to (smallest weight), then others.
- Once you have exhausted a vertex, go to the next smallest working value.