Question 2

Question 2.
Perfect Complete Graph
(a) To prove that a directed graph is a Perfect Complete Graph if and only if between any pair of
vertices, there is at most one edge, and for all k ∈ {0, 1, . . . , n - 1}, there exists a vertex v in
the graph such that Outdegree(v) =k, for this I’ll prove two parts:
Part 1: If the graph is a Perfect Complete Graph, then between any pair of vertices, there is
at most one edge, and for all k ∈ {0, 1, . . . , n - 1}, there exists a vertex v in the graph such
that Outdegree(v) = k.
1. Between any pair of vertices, there is at most one edge:
If the graph is a Perfect Complete Graph, then by definition, there is exactly one directed
edge between every pair of distinct vertices. Therefore, between any pair of vertices, there is
at most one edge.
2. For all k ∈ {0, 1, . . . , n - 1}, there exists a vertex v in the graph such that Outdegree(v) = k:
Let's consider an arbitrary k ∈ {0, 1, . . . , n - 1}. Since the graph is a Perfect Complete Graph,
every vertex is connected to every other vertex with exactly one edge. Therefore, for any
vertex v, there are n - 1 other vertices that have an edge going out from v. This satisfies
Outdegree(v) = n - 1. Additionally, there are n - 1 vertices that have an edge going into v, so
this also satisfies Indegree(v) = n - 1.
Now, consider removing any one of the edges connected to v. The outdegree of v becomes
n - 2. This process can be repeated until the outdegree of v becomes k, satisfying the
condition for any k ∈ {0, 1, . . . , n - 1}.
Part 2: If between any pair of vertices, there is at most one edge, and for all k ∈ {0, 1, . . . , n -
1}, there exists a vertex v in the graph such that Outdegree(v) = k, then the graph is a Perfect
Complete Graph.
Now, I’ll show that the given conditions imply that the graph is a Perfect Complete Graph.
1. There is exactly one directed edge between every pair of distinct vertices:
Suppose there are two directed edges (a, b) and (b, a) between vertices a and b. Since
there is at most one edge between any pair of vertices, it implies that a = b, which
contradicts the assumption that I’m dealing with distinct vertices.
2. For any three vertices a, b, c, if (a, b) and (b, c) are directed edges, then (a, c) is present
in the graph:
Let's assume there are directed edges (a, b) and (b, c) in the graph. Since there is at
most one edge between any pair of vertices, it implies that there cannot be any other
edges between a and b, and b and c.
Now, consider the outdegree of b. By the given condition, there exists a vertex v such that
Outdegree(v) = k, where k can be any value from 0 to n - 1. If k = 0, then there are no edges going out
from b, which contradicts the fact that (a, b) and (b, c) are directed edges. Therefore, k > 0. But if k >
0, it implies that there are edges going out from b. Since there is at most one edge between any pair
of vertices, the only possibility is that k = 1, and there is exactly one edge going out from b.
Therefore, (a, c) must be present in the graph, satisfying the Perfect Complete Graph condition.
This completes the proof that a directed graph is a Perfect Complete Graph if and only if between
any pair of vertices, there is at most one edge, and for all k ∈{0, 1, . . . , n - 1}, there exists a vertex v
in the graph such that Outdegree(v) = k.
(b) To check if a given directed graph represented by its adjacency matrix is a perfect complete
graph, I’ll use the characterization provided in part (a) of the question. Here's an algorithm
to achieve this in O(n^2) time complexity:
1. Check if there is at most one edge between any pair of vertices:
Iterate through the adjacency matrix and for each pair of vertices (i , j), check if the value at
matrix[i][j] is 0 or 1. If it is 1, continue to the next step. If it is greater than 1, the graph is not
a perfect complete graph. Return false.
2. Check if for all k in {0, 1, ..., n-1}, there exists a vertex v such that Outdegree(v) = k:
Iterate through each row of the adjacency matrix and count the number of 1s in each row. If
for any row, the count is not equal to k (where k is the index of the row), the graph is not a
perfect complete graph. Return false.
3. If both conditions are satisfied for all vertices, return true. The graph is a perfect
complete graph.
Pseudo Code:
function is_Perfect_Complete_Graph(adj_Matrix):
n = size(adj_Matrix)
// Step 1: Check if there is at most one edge between any pair of vertices
for i from 0 to n-1:
for j from 0 to n-1:
if adj_Matrix[i][j] > 1:
return False
// Step 2: Check if for all k in {0, 1, ..., n-1}, there exists a vertex v such that Outdegree(v) = k
for i from 0 to n-1:
outdegree = 0
for j from 0 to n-1:
outdegree = outdegree + adj_Matrix[i][j]
if outdegree != i:
return False
return True
Time Complexity Analysis:
1. Checking if there is at most one edge between any pair of vertices: This step takes O(n^2)
time as it’s iterating through the entire adjacency matrix of size n x n.
2. Checking if for all k in {0, 1, ..., n-1}, there exists a vertex v such that Outdegree(v) = k: This
step also takes O(n^2) time as it’s iterating through each row of the adjacency matrix and
counting the number of 1s in each row.
Therefore, the overall time complexity of the algorithm is O(n^2).

Question 2

Uploaded by

Copyright:

Available Formats

Question 2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Question 2

Uploaded by

Copyright:

Available Formats

Question 2.

Perfect Complete Graph

for i from 0 to n-1:

for j from 0 to n-1:

for i from 0 to n-1:

for j from 0 to n-1:

outdegree = outdegree + adj_Matrix[i][j]

Time Complexity Analysis:

Therefore, the overall time complexity of the algorithm is O(n^2).

You might also like