Question 1 (1 point) When repesenting a graph as an adjacency list, space is sav

Question

Question 1 (1 point) When repesenting a graph as an adjacency list, space is saved compared to representation as an adjacency matrix. 1) True 2) False Save Question 2 (1 point) The following are the degrees of each vertex in a simple graph in decreasing order There are no loops). Is this graph possible (True Yes, False-No)? 6, 6, 6, 6, 3,3, 2,2 1) True 2) False Save Question 3 (1 point) A random undirected graph has 9 vertices. An unordered cycle is a connection within the graph that connects a number of vertices. For example an unordered cycle of 3 would be a triangle within the graph of 3 connected vertices. To find the total number of possible unordered cycles of 3 vertices from the total you can use the Combination Formula C(n,r) n!/r(n-r)! which is total number of possible combinations of r objects from a set of n objects. If the probability of an edge between any two vertices is 100% (all vetices connected)-what is the expected number of unordered cycles of length 3? 4 2) 10 3) 20 4) 35 5) 56

Explanation / Answer

Q1) When representing a graph as an adjacency list, space is saved compared to representation as an adjacency matrix.

Answer)

True

When representing a graph as an adjacency list the space required is O(V^2), but on the representation as an adjacency matrix it saves space in O(|V|+|E|). So the above statement is True.

Q2) The following are the degrees of each vertex in a simple graph in decreasing order. Is the graph possible?

Answer)

6,6,6,6,3,3,2,2

True, the graph is possible with degrees 6,6,6,6,3,3,2,2.

The graph would be :

(0) (1) (2) (3) (4) (5) (6) (7)

(0) 0 1 1 1 1 1 1 0

(1) 1 0 1 1 1 1 1 0

(2) 1 1 0 1 1 1 0 1

(3) 1 1 1 0 0 0 0 1

(4) 1 1 1 0 0 0 0 0

(5) 1 1 1 0 0 0 0 0

(6) 1 1 0 0 0 0 0 0

(7) 0 0 1 1 0 0 0 0

Q4) Maximum number of edges in a acyclic undirected graph with n vertices?

Answer)

As we have a acyclic undirected graph with n vertices, the acyclic graph is a spanning tree and thus the maximum number will be n-1 edges.

Q5) The following are the degrees of each vertex in a simple graph in decreasing order. Is the graph possible?

Answer)

7,6,6,4,4,3,2,2

True, the graph is possible with degrees 7,6,6,4,4,3,2,2

The graph would be:

(0) (1) (2) (3) (4) (5) (6) (7)

(0) 0 1 1 1 1 1 1 1

(1) 1 0 1 1 1 1 1 0

(2) 1 1 0 1 1 1 0 1

(3) 1 1 1 0 1 0 0 0

(4) 1 1 1 1 0 0 0 0

(5) 1 1 1 0 0 0 0 0

(6) 1 1 0 0 0 0 0 0

(7) 1 0 1 0 0 0 0 0

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.