(i)[1 pt.] Let s be the sum of the entries in a certain row of an adiacency matr
ID: 3737345 • Letter: #
Question
(i)[1 pt.] Let s be the sum of the entries in a certain row of an adiacency matrix of an undirected graph G, and let v be the vertex of G which corresponds to that particular row of the matrix. Consider the following statements S1, S2, S3, and S4 about the number s and the vertex v: SI: If v is an isolated vertex of G, then s0 S2: Ifs 0, then vis an isolated vertex of G. TSa» SAm S3: If G has no loop at v, then s is equal te the degree of v in G S4: If G has a loop at v, then s is less than the degree of v in G Write down the label (S1, S2, S3, or S4) of each true statement. If none of these statements is true, write "ALL FALSE". ANSWER: ,23 ii)[1 pt.] Now let s be the sum of the entries in a certain row of an incidence matrix of an undirected graph G, and let v be the vertex of G which corresponds to that particular row of the matrix. Consider the foltowing statements S1, S2, S3, and S4 about s and the vertex v: SI: lf v is an isolated vertex of G, then s 0 S2: Ifs-0, then v is an isolated vertex of G S3: If G has no loop at v, then s is egual to the degree of v in G S4: If G has a loop at v, then s is less than the degree of v in G Write down the label (S1, S2, S3, or S4) of each true statement. If none of thesc statements is true, write "ALL FALSE". ANSWER ii)[1 pt.] Now let s be the sum of the entries in a certain row of an adiacency matrix of a directed graph G, and let v be the vertex of G which corresponds to that particular row of the matrix. Consider the following statements S5, S6, S7, and S8 about s and the vertex v S5: If G has no loop at v, then s is equal t the indegree of v in G. S6: If G has a loop at v, then s is less than the indegree of v in G S7: If G has no loop at v, then s is equaltthe outdegree of v in (G S& [f G has a loop at 1, then s is less than the outdegree of r in G Write down the label (S5, S6, S7, or S8) ofeachtre statement. If none of these statements is true, write "ALL FALSE". ANSWER v)[1 pt.] Now let s be the sum of the entries in a certain colum of an adjacency matrix ofa directed graph G, and let v be the vertex of G which corresponds to that particular column of the matrix. Consider the following statenents S5, S6, S7, and S8 about s and the vertex v: 55 If G has no loop at v, then s is equal to the indegree of)' In G S6: If G has a loop al v, then s is less than lhe indegree of v in S7: If G has no loop at v, then is equal the outdegree of v in G S8: If G has a loop at v, then s is less than the outdegree of v in G Write down the label (S5, S6, S7, or S8) of each true statement. If none of these statements is true, write "ALL FALSE". ANSWER: )[I pt.] Now let s be the sum of the entries in a certain column of an incidence matrix of arn undirected graph G, and let e be the edge ol G which corresponds to that particular columin of the matrix. Consider the following statements S9, Si0, S11, and S12 about s and the edge e: s cannot be equal to 3 S10: If e is a loop of G, then s1. S11:ifs- 1,then e is a loop ofG S12: s cannot be equal to 0 Write down the labcl (S9, S10, S11, or S12) of each true statement. If none of these statements is true, write "ALL FALSE". ANSWER:Explanation / Answer
Solution:
i)
S1 S2 S3
Explanation:
The sum of any row in an adjacency list is the degree of that particular vertex, and an isolated vertex degree is always 0.
S4 is wrong because in that case there will be an entry on the diagonal element of the row
ii)
S1, S2, S3, S4
iii)
S7
iv)
S5
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.