W12- graph theory 2

Question 1

Tree and theorms of trees

Answer 1

A tree is a connected graph without cycles.

• A graph G=(V,E) is a tree if and only if it is a minimal connected graph on V. That is, Removing any edge destroys the connectivity of G
• Every tree with at least two vertices has a leaf (vertex belongs to exactly one edge)
• For every n∈N, every tree on n vertices has n−1 edges.

Question 2

What is a Forest and properties of Forests

How many edges does a forest have?

Answer 2

A forest is just a graph with no cycles.
* In other words, it is like a tree, except that we don’t require it to be connected.
* A forest is a collection of trees.
* For every n∈N, every forest with n vertices and k componesnts has n−k edges.

Question 3

What is a Spanning tree

Answer 3

Let G be a connected graph.
A spanning tree is a subgraph of G which
* Is a tree
* Includes every vertex of G

Question 4

Kruskal’s greedy algorithm to find MST

Answer 4

1. Sort all edges
2. Pick the smallest edge and put in the MST, such that it does not create a cycle
3. If it does create a cycle, pick the next smallest edge
4. Repeat step 2 and 3 until all vertices are in the MST (until number of edges =v−1)

Question 5

Planar graphs meaning

And formulas for planner graphs

Which formula to use to prove that it is a Planar graph?

Answer 5

Planner graph is a graph that can be drawn without any edges crossing (but in the current drawing of the graph, it does not necessary have to show it)
* Planner drawing shows that the graph can be drawn without any edges crossing

Let n=vertices, m=edges, f=faces
If a graph is planner then:
* n−m+f=2
* m≤3n−6

Use m≤3n−6 to prove if a graph is planer or not