I need answers 1. Neighbors Choose one node, then find its in-neighborhood, out-

Question

I need answers

1. Neighbors Choose one node, then find its in-neighborhood, out-neighborhood, in-degree and out-degree 2. Sources and sinks: Which nodes are sources and which are sinks (if any)? 3. Connectivity: Is it weakly connected? . Is it strongly connected? Is it rooted i.e., does it contain a rooted spanning tree)? . Does it contain a globally reacheable node? 4. Find its strongly connected components 5. Draw its condensed digraph C(G) 6. Adjacency matrix: Write the adjacency matrix of C(G), having chosen vertex labels in such a way that this adjacency matrix is triangular (hint: start from sources, and end with sinks Write the adjacency matrix of G, having chosen vertex labels in such a way that this adjacency matrix is triangular (hint: keep components ordered as in the condensed digraph)

Explanation / Answer

First spot the vertices in the given graph.

1Ans:

In the given graph

in- neighbourhood Thegiven graph is directed graph.

In Neighbourhood : HKL, IJH,ABC,FEG degree is 3

Out neighbour hood: JKH, IJH degree is 3

2 Ans; a directed graph with no cycles has at least one source and one sink.

A vertex with an indegree of 0 is called a source (since one can only leave it) and a vertex with an outdegree of 0 is called a sink (since one cannot leave it).

Sourec vertext is A

Sink vertexes are K, L, G,I

3 Ans:

A graph is connected when there is a path between every pair of vertices

The given graph is strongly connected because there is no week connectiveity.

It is rooted means this is an directionla graph with clear indices.

It contians a reched node K and L with globally connected.

Strongly connect components are:

ABC, EGF, IJH,LKJH

weekly conectd components are :

F,H

Adjacency matrix for the given graph:

A B C D E F G H I J K L A 0 1 0 1 0 0 0 0 0 0 0 0 B 0 0 1 0 0 0 0 0 0 0 0 0 C 1 0 0 0 0 0 0 0 0 0 0 0 D 0 0 0 0 0 1 0 0 0 0 0 0 E 0 0 0 0 0 1 1 0 0 0 0 0 F 0 0 0 0 0 0 0 0 0 0 0 0 G 0 0 0 0 0 1 0 0 0 0 0 0 H 0 0 0 0 0 0 0 0 1 1 0 0 I 0 0 0 0 0 0 0 0 0 1 0 0 J 0 0 0 0 0 0 0 0 0 0 1 0 K 0 0 0 0 0 0 0 1 0 0 1 0 L 0 0 0 0 0 0 0 1 0 0 0 0

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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