For each part, give a brief one-sentence answer. (a) Consider a particular fores
ID: 3833256 • Letter: F
Question
For each part, give a brief one-sentence answer. (a) Consider a particular forest, and make a graph where each vertex is a different animal species that lives in that forest. There is an edge from A to B if A is known to eat B. For example, if there are owls and mice in this forest then there would be an edge from the owl vertex to the mouse vertex. i. Explain why this graph is a directed graph. ii. What is the definition of the indegree of a vertex and what is its meaning in this graph? iii. What is the definition of the outdegree of a vertex and what is its meaning in this graph? iv. What is the definition of a source and what would it mean if this graph has a source? v. What is the definition of a sink and what would it mean if this graph has a sink? vi. What does it mean if this graph has a cycle? vii. What does it mean if there is a path from A to B? (b) Consider a graph where each vertex is a student at UCSD, and there is an edge from A to B if A and B are taking the same class this quarter. i. Explain why this is an undirected graph. ii. How would you interpret the meaning of the degree of a vertex in this graph? iii. Estimate the degree of the vertex that represents you. iv. Briefly describe a situation in which this graph would have more than one connected component.Explanation / Answer
(a)
In a forest, a graph is made where each vertex is a different animal species that lives in that forest. There is an edge from A to B if A is known to eat B. For example, if there are owls and mice in this forest then there would be an edge from owl vertex to the mouse vertex.
i.
This graph is a directed graph because there will be an edge from the vertex OWL to vertex MOUSE because the owl will eat the mouse so the edge will be directed. Hence, direction is important to specify that the owl eats mouse.
ii.
An indegree is the number of edges pointing inwards to a particular edge, it means the number of arrow heads pointing towards that vertex and with respect to this graph it means the number of animals which are going to eat that animal which is pointed to by the arrow.
iii.
An outdegree of a graph means the number of edges moving outwards from a particular edge. With respect to this graph it means the number of animals that a particular animal can eat.
iv.
A source of a graph is a node that has only outgoing edge but no incoming edges. With respect to this graph, a source means that an animal cannot be eaten by any other animal.
v.
A sink means that the node has only incoming edges but no outgoing edges. With respect to this graph, a sink represents an animal which cannot eat any other animal and is eaten by all animals which have edges directed towards that animal which has sink.
vi.
If the graph has a cycle, it means that if an animal X is eaten by another animal Y, then X can also eat the animal Y.
vii.
If there is a path from a vertex A to the vertex B, it means that there exists a relationship between the two vertices.
(b)
On considering a graph where each vertex is a student at UCSD, and there is an edge from A to B if A and B are taking the same class this quarter
i.
This is an undirected graph because there is no need to specify whether the flow of direction is from A to B or B to A because an edge can occur only when A and B are taking the same class this quarter.
ii.
The degree of a vertex in this graph with respect to the situation represents the number of students who are taking the same class in this quarter.
iii.
The degree of the vertex that represents you is one for a set of vertices if there exists an edge from the set of vertices.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.