Chapter 2 Graph Theory Flashcards
What is definition of a connected graph
Where each node can TAKE AN INDIRECT path to get to all other nodes
So there is a path that can connect one node to another somehow
What are having multiple edges or a loop?
Multiple edge = two edges or more going from one node to another
Loop = a loop around one node , takes back to same node (so like website on homepage click on something takes back to homepage)
What is a SIMPLE graph
A graph with NO LOOPS or MULTIPLE EDGES
Remember do simple graphs need to be connected?
NO, they can just be inviduak nodes on their own, so that can give extra variants
What is a COMPLETE GRAPH
a graph where ALL THE NODES are all connected DIRECTLY TO EACH OTHER
What is the formula , Kn for the minimum number of EDGES in a complete graph with n nodes and how to find out
= 1/2n (n-1)
Start with n= 2 = 1 node
N=3 = 3 node
N=4 = 6 node (draw them out)
This is triangle number = 1/2n (n+1)
HOWEVER sequence starts at 2 rather than one, so need to shift whole seauence back one = 1/2n (n-1)
Again what’s the nth term for the minimum number of edges Kn for a complete graph with n nodes
1/2n (n-1)
What is a Bipartite graph
What does it mean when it says find a complete matching
What’s the best way to do this
What is a COMPLETE bipartite graph
This is when you have two subsets of nodes, which CAN NOT BE CONNECTED TI EACH OTHER IN SAME SET, and these connected across Esch other
Could represent a group of workers and the jobs they can do, some can do multiple
2) this is when each worker has one task (do by inspection algorithm not needed)
- MATCH THE TASK THATS UNIQUE TO A WORKER FIRST, then complete the rest
3) this is where each node on left is connected to every node in right
Notation for complete bipartite graph?
K, r,s what this mean
K, r, s
Means r nodes on left all connected to s nodes on right
Remember to circle Esch subset on left snd right when drawing bipartite graphs!
Two circles thus, shows they are separate
What does ORDER / degree of a vertex mean
What about for a loop?
It means the NUMBER OF ROUTES COMING OUT OF THE NODE
For a loop, there are still two different ways you can take (left right, think like benzene cover it)
So two ways out of a loop!
Okay so defintions for simply connected vs complete
Simple = no loops or multiple edges
Connected = all nodes are indirectly connected to esch other
Complete = all nodes are directly connected to each other
So simply connected means connected graoh with no loops edges, but not all nodes have to be connected to Esch other
What’s definition if a tree then
A SIMPLY CONNECTED (not complete) graoh with the MINIMUM NUMBER OF EDGES
(The minimum number if edges removed the complete)
For n nodes of a tree, what’s the NUMBER OF EDGES IT WILL HAVE
Try and derive for 2 3 4
= n-1
What’s a cycle in a graoh
Do trees have these!
Where you can go around and around ,
Trees have NO CYCLES, as this makes it not minimum arcs for simple connected
