Graphs (Part E)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
April 06, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 1 / 17
1 Planar Graphs
2 Graph Coloring
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 2 / 17
Planar Graphs
Definition: Planar Graph
A graph is called planar if it can be drawn in the plane without any edges crossing. A crossing of edges is the point of intersection of the lines. Such a drawing is called a planar representation of the graph.
Note: A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a different way without crossings.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 3 / 17
Non-planar Graphs
Example: Non-planar Graph
Figure: A distributed architecture for network resource auctioning (K3,3).
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 4 / 17
Euler’s Formulae
A planar representation of a graph splits the plane into regions, including an unbounded region.
Theorem 1: Euler’s Formula
Let G be a connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G. Then r = e − v + 2.
Corollary 1
If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then e ≤ 3v − 6.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 5 / 17
Euler’s Formulae (cont.)
Corollary 2
If G is a connected planar simple graph, then G has a vertex of degree not exceeding five.
Corollary 3
If a connected planar simple graph has e edges and v vertices with v ≥ 3 and no circuits of length three, then e ≤ 2v − 4.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 6 / 17
Kurotowski’s Theorem
Elementary Subdivision
If a graph is planar, so will be any graph obtained by removing and edge {u, v} and adding a new vertex w together with edges {u, w} and {w, v}.
Homeomorphism
The graphs G1 = (V1, E1) and G2 = (V2, E2) are called homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivision.
Kurotowski’s Theorem
A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 and K5.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 7 / 17
Applications of Planar Graphs
• Electronic circuit board printing
• Roads and highway network designing
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 8 / 17
Graph Coloring
Definition: Coloring
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.
Definition: Chromatic Number
The chromatic number of a graph is the least number of colors needed for a coloring of this graph. The chromatic number of a graph G is denoted by χ(G).
The Four Color Theorem
The chromatic number of a planar graph is no greater than four.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 9 / 17
Applications of Colorings
• Scheduling: exams, tasks, …
• Assignments: spectrum allocation • Resource allocation
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 10 / 17
Definition: Tree
A tree is a connected undirected graph with no simple circuits. Definition: Forest
A forest is a graph that has no simple circuit, but is not connected. Each of the connected components in a forest is a tree.
An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 11 / 17
Rooted Trees
Definition: Rooted Tree
A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.
• If v is a vertex of a rooted tree other than the root, the parent of v is the unique vertex u such that there is a directed edge from u to v. When u is a parent of v, v is called a child of u. Vertices with the same parent are called siblings.
• The ancestors of a vertex are the vertices in the path from the root to this vertex, excluding the vertex itself and including the root. The descendants of a vertex v are those vertices that have v as an ancestor.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 12 / 17
Rooted Trees (cont.)
• A vertex of a rooted tree with no children is called a leaf. Vertices that have children are called internal vertices.
• If a is a vertex in a tree, the subtree with a as its root is the subgraph of the tree consisting of a and its descendants and all edges incident to these descendants.
Definition: m-ary Tree
A rooted tree is called an m-ary tree if every internal vertex has no more than m children. The tree is called a full m-ary tree if every internal vertex has exactly m children. An m-ary tree with m = 2 is called a binary tree.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 13 / 17
Ordered Rooted Trees
• An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered.
• In an ordered binary tree, if an internal vertex has two children, the first child is called the left child and the second child is called the right child.
• The tree rooted at the left child of a vertex is called the left subtree of this vertex.
• The tree rooted at the right child of a vertex is called the right subtree of this vertex.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 14 / 17
Properties of Trees
Theorem 2: No. of Edges
A tree with n vertices has n − 1 edges. Theorem 3: No. of Vertices
A full m-ary tree with i internal vertices contains n = mi + 1 vertices. Theorem 4: m-ary Tree
An full m-ary tree with
(i) n vertices has i = (n − 1)/m internal vertices and l = [(m − 1)n + 1]/m leaves,
(ii) i internal vertices has n = mi + 1 vertices and l = (m − 1)i + 1 leaves, (iii) l leaves has n = (ml − 1)/(m − 1) vertices and i = (l − 1)/(m − 1) internal vertices.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 15 / 17
Properties of Trees (cont.)
Theorem 4: Height
There are at most mh leaves in an m-ary height h. Corollary
If an m-ary tree of height h has l leaves, then h ≥ ⌈logm l⌉. If the m-ary tree is full and balanced, then h = ⌈logm l⌉.
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 16 / 17
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 10e MdH W22 April 06, 2022 17 / 17
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com