Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
Graph theory (directed graphs) question?
I'm having trouble with this problem.
A graph has 6 vertices, and 12 edges, each of them directed. Each vertex has order 4 - 2 edges leaving it, and 2 edges entering it.
I'm supposed to design a graph so that no vertex is more than two steps (via the directed edges, i.e. can only travel in the direction each edge is pointing) from any other vertex.
In addition (and this is the hard part), I should be able to remove any vertex from the graph (and any any edges associated with it), and each of the remaining 5 vertices must be no more than three steps (via the remaining 8 directed edges) from any other vertex.
I've found a number of 6 vertex graphs that satisfy the first condition, but I can't get ANY to work for the second condition (i.e. removing one vertex). Anyone have an idea?
1 Answer
- Doc BLv 61 decade agoFavorite Answer
Start with a triangular prism, one triangle above the other. The up/down edges of the prism become a pair of directed edges, one in each direction. The edges of the top triangle are traversed clockwise; the edges of the bottom triangle are traversed counter-clockwise.
That is, with nodes 1...6, the edges are (1,2), (2,3), (3,1), (1,4), (4,1), (2,5), (5,2), (3,6), (6,3), (4,6), (6,5), (5,4).
Is there a particular application in mind?
