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
What is network simple definition
Just a network with weigths in nodes, which could represent time, cost etc
What’s a MINIMUM SPANNING TREE
How do we find these solutions ( algorithms ?)
this is a TREE (simple connected minimum arc + no cycle)
+ where its connected with the LEAST AMOUNT OF TOTAL WEIGHT to get everyhwere
To find these solutions we use Kruskal and prims algorithms
How to do incidence matrix
How many ways is a loop connected to itself!
Incidence matrix =
- write down all nodes labelled as row and column
- then A with A just means how many ways is A connected to A
Fill this out and there WILL BE SYMMETRY along diagonal,
2) loop connected 2 TIMES DONT LACM
What does isomorphic mean
Where two graphs are the same after manipulating how they look as long as edges not added or broken
What will incidence matrix look like for two ISOMOROPHIC GRAPHS
Same exact incidence matrix !
