The answers listed strongly connected components in this graph. But the textbook said a strongly connected component is a strongly connected subgraph of the directed graph but not contained in larger strongly connected subgraphs.
I do not see how the subgraph of this graph is strongly connected because the textbook said strongly connected means there is a path from vertices a to b. But there is no such thing because the directed edges clearly shows that.
Strongly connected means if you can go from A->B you can also go from B->A? (EDIT: That doesn't mean you can go from A to B and vice versa in one hop. one way systems would suck then ;) )
The graphs don't have to be connected in that case. You can have 2 or more subgraphs which aren't connected. Disjointed graphs are fine.
EDIT2: I think it means you get rid of dead ends.
Strongly connected means if you can go from A->B you can also go from B->A? (EDIT: That doesn't mean you can go from A to B and vice versa in one hop. one way systems would suck then ;) )
The graphs don't have to be connected in that case. You can have 2 or more subgraphs which aren't connected. Disjointed graphs are fine.
I'm a bit confused when the textbook says A to B are they saying A is the initial vertex and B is the terminal vertex? Or is A, a vertex labeled A and B, a vertex labeled B?
It means any 2 vertices (could even be the same vertex, unless implicitly stated this is disallowed). Don't be confused by "if you can get from A to B" thinking the meaning is "you can get from vertex "a" to vertex "b"".
Maths books hardly ever have numbers in them, they generalise.
In that graph you can go from a to b and vice versa though ;) - just follow the arrows between them.
EDIT: In the graph you posted, vertex "e" is a dead end so isn't strongly connected to the others, if I am correct in my guess at what strongly connected means. I'm not sure whether the strongly connected components are
{e} and G\{e}
or
{e} and G
(where G is the entire graph).
It means any 2 vertices (could even be the same vertex, unless implicitly stated this is disallowed). Don't be confused by "if you can get from A to B" thinking the meaning is "you can get from vertex "a" to vertex "b"".
Maths books hardly ever have numbers in them, they generalise.
In that graph you can go from a to b and vice versa though ;) - just follow the arrows between them.
Yeah, it does go from vertex "a" to vertex "b" and vice-versa. which means it is strongly connected which would mean it is a strongly connected component. But the textbook did not list that as an answer.
Ok well see my edit, the answer is either
{e} and G\{e}
or
{e} and G,
depending on the definition, which I'm too lazy too google (6th beer).
Ok well see my edit, the answer is either
{e} and G\{e}
or
{e} and G,
depending on the definition, which I'm too lazy too google (6th beer).
the strongly connected components are {a, b, f }, {c, d, e}.
I am using Rosens' textbook.
Mhmm ok, I can see now that once you go to vertex "c" you can never get back to {a, b, f}.
That's what it means then, in effect. Strongly connected means you can get from place to place but if you leave your neighbourhood and can never get back that is a new subgraph.
They are basically talking about dead ends and one way streets.
EDIT: I'm interested why {e} doesn't count on its own though? Once you get to {e} you are stuck...
EDIT2: I see you can get back to {c} from {e}. Ignore this drunkard ;) I guess we've both learned something today!
Mhmm ok, I can see now that once you go to vertex "c" you can never get back to {a, b, f}.
That's what it means then, in effect. Strongly connected means you can get from place to place but if you leave your neighbourhood and can never get back that is a new subgraph.
They are basically talking about dead ends and one way streets.
EDIT: I'm interested why {e} doesn't count on its own though? Once you get to {e} you are stuck...
EDIT2: I see you can get back to {c} from {e}. Ignore this drunkard ;)
I am not sure what they mean by {a,b,f}
because once you go from vertex labeled a to vertex labeled b, after vertex b you cannot go to vertex f based off the graph.
Sure you can, you go b->a->f. Like I said, you don't have to do it in one hop.
EDIT: Mind blowing time! You don't even need to do it in a finite number of hops, probably ;)
