Kumpulan Soal Latihan Matematika Diskrit I

Struktur Diskrit : Terminologi Graf, The Handshaking Theorem, dan Tipe Graf Spesial

Graph Terminology

• Adjacent 
• Incident 
• Neighbor 
• Degree 
• Isolated 
• Pendant
• Initial Vertex
• Terminal 
• In-Degree / Out-Degree 
• Bipartite 
• Subgraph

Adjacent and Incident

Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge of G.

If the edge e is associated with (u, v), e is called incident with the vertices u and v (e connects u and v).

Example :

• a and b are adjacent
• a and c not adjacent
• e2 incident with a and b

Degree, Isolated and Pendant

The degree of a vertex in an undirected graph is the number of edges incident with it. The degree of the vertex v is denoted by deg(v).

The set of all neighbors of a vertex v of G = (V , E), denoted by N(v), is called the neighborhood of v.

A loop at a vertex contributes twice to the degree of that vertex. A vertex of degree zero is called isolated (not adjacent to any vertex). A vertex is pendant if it has degree one.

Example 1

What are the degrees and what are the neighborhoods of the vertices in the graphs G ? 

• deg(a) = 2, 
• deg(b) = deg(c) = deg(f) = 4, 
• deg(d ) = 1, 
• deg(e) = 3, 
• deg(g) = 0.

• N (a) = {b, f }, 
• N (b) = {a, c, e, f }, 
• N (c) = {b, d, e, f }, 
• N (d) = {c}, 
• N (e) = {b, c, f }, 
• N (f ) = {a, b, c, e}, 
• N (g) = ∅.

Example 2

What are the degrees and what are the neighborhoods of the vertices in the graphs H ? 

• deg(a) = 4, 
• deg(b) = deg(e) = 6, 
• deg(c) = 1, 
• deg(d ) = 5.

• N (a) = {b, d, e}, 
• N (b) = {a, b, c, d, e}, 
• N (c) = {b}, 
• N (d) = {a, b, e}, 
• N (e) = {a, b, d}.

Theorem involving Degrees

The Handshaking Theorem

Let G = (V, E) be an undirected graph with e edges. Then

This theorem also applies if multiple edges and loops are present. An undirected graph has an even number of vertices of odd degree.

Example 3

How many edges are there in a graph with 10 vertices each of degree 6 ?

Because the sum of the degrees of the vertices is 6 · 10 = 60, it follows that 2m = 60 where m is the number of edges. Therefore, m = 30.

Initial and Terminal Vertex

When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u. The vertex u is called the initial vertex of (u, v), and v is called the terminal or end vertex of (u, v).

The initial vertex and terminal vertex of a loop are the same.

Example 

• a is adjacent to b 
• b is adjacent to c 
• Vertex a is initial vertex of (a, b) 
• Vertex b is terminal vertex of (a, b) 

In-Degree and Out-Degree

For directed graph :

• The in-degree of a vertex v, denoted by deg⁻ (v), is the number of edges with v as their terminal vertex.
• The out-degree of a vertex v, denoted by deg⁺ (v), is the number of edges with v as their initial vertex.

Loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex. 

The summation :

Example 4

Find the in-degree and out-degree of each vertex in the graph G ! 

The in-degrees in G are

• deg−(a) = 2, 
• deg−(b) = 2, 
• deg−(c) = 3, 
• deg−(d) = 2, 
• deg−(e) = 3, and 
• deg−(f ) = 0.

The out-degrees are 

• deg+(a) = 4, 
• deg+(b) = 1, 
• deg+(c) = 2, 
• deg+(d) = 2, 
• deg+(e) = 3, and 
• deg+(f ) = 0.

Some Special Simple Graphs

• Complete Graph
• Cycles
• Wheels
• n-Cubes

Complete Graph

The Complete Graph on n vertices, denoted by Kn, is the simple graph that contains exactly one edge between each pair of distinct vertices. 

Example: the graph Kn for 1 ≤ n ≤ 5.

Cycles

The Cycle Cn, n ≥ 3, consists of n vertices v1, v2, … vn and edges {v1, v2}, {v2, v3}, …, {vn-1,vn} and {vn, v1}.

Example: the Cn for 3 ≤ n ≤ 6.

Wheels

The Wheel Wn, n ≥ 3, is obtain when we add an additional vertex (usually at the center) to the cycle Cn and connect this new vertex to each of the n vertices in Cn by new edges.

Example: the Wn for 3 ≤ n ≤ 6.

N-Cubes

The n-dimensional hypercube, or n-cube, denoted by Qn, is the graph that has vertices representing bit strings of length n.

Example: the graph Qn for 1 ≤ n ≤ 3.

Bipartite Graphs

A simple graph G is called bipartite if the vertex set V can be partitioned into two disjoint (nonempty) sets V1 and V2, so every edge in G is incident with a vertex in V1 and a vertex in V2. We call the pair (V1, V2) a bipartition of the vertex set V of G.

Example 1: C6 is bipartite

Let V1 = {a, c, e} 

Let V2 = {b, d, f}

Every edge of C6 connects a vertex in V1 and V2

Example 2: W4 is not bipartite

Let V1 = {a, c, e} 

Let V2 = {b, d}

Edge (a, e) of W4 not connects a vertex in V1 and V2

Example 5

Are the graphs G and H bipartite ?! 

Graph G is bipartite because its vertex set is the union of two disjoint sets, {a, b, d} and {c, e, f, g}, and each edge connects a vertex in one of these subsets to a vertex in the other subset

Graph H is not bipartite because its vertex set cannot be partitioned into two subsets so that edges do not connect two vertices from the same subset.

Complete Bipartite Graphs

Let G be a bipartite graph with |V1| = m and |V2| = n. If an edge runs between every vertex in V1 and V2, G is a complete bipartite graph, denoted by Km,n.

Example : 

• K2,3 
• K3,3 
• K3,5 
• K2,6 

Complete Matching and Maximum Matching

A maximum matching is a matching with the largest number of edges. 

We say that a matching M in a bipartite graph G = (V , E) with bipartition (V1, V2) is a complete matching from V1 to V2 if every vertex in V1 is the endpoint of an edge in the matching, or equivalently, if |M| = |V1|. 

Example 6

Find a maximum matching for this job assignment !

Marriage on an island

Suppose that there are m men and n women on an island. Each person has a list of members of the opposite gender acceptable as a spouse. 

We construct a bipartite graph G = (V1, V2) where V1 is the set of men and V2 is the set of women so that there is an edge between a man and a woman if they find each other acceptable as a spouse. 

A matching in this graph consists of a set of edges, where each pair of endpoints of an edge is a husband-wife pair. 

A maximum matching is a largest possible set of married couples, and a complete matching of V1 is a set of married couples where every man is married, but possibly not all women. 

Applications of Special Types of Graph

Local Area Network

Illustrate the connection between various computers and devices

Star topology : K1,n

All devices connected to a central control device

Ring topology : n Cycles (Cn)

Each device is connected to exactly two others

Hybrid topology : star + ring

Redundancy makes the network more reliable

New graphs form Old

Subgraph

A subgraph of a graph G = (V, E) is a graph H = (W, F), where W ⊆ V and F ⊆ E . A subgraph H of G is a proper subgraph of G if H ≠ G.

Union of Graphs

The Union of two simple graphs G1 = (V1, E1) and G2 = (V2, E2) is the simple graph with vertex set V1 ∪ V2 and edge set E1 ∪ E2 . The union of G1 and G2 is denoted by G1 ∪ G2 .

Sumber

Slide Strukdis : Terminologi Graf

http://informatika.unpar.ac.id/