Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

While studying discrete maths I was having difficult to understand the following definition:

Here is a definition about connected graphs from the book Ralph Grimaldi - Discrete and Combinatorial Mathematics - 5ed.

(from page 517)

What I can't understand is the second property/definition, the one that says, when you have a directed graph, then if the associated undirected graph is connected, that implies that the directed graph will be connected too.

I could easily draw an example when this doesn't occurs: enter image description here

(2) is the undirected associated graph and IT'S CONNECTED.

But, I don't agree about that, I don't see how (1) can be connected too, because you don't have a path from d to a for example.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

I'll answer my own question because I find out where my thinking was wrong and also I found an alternative definition.

The following article explain the same as Grimaldi does, but calls it "weak connected" instead of just "connected", also defines the property of "connected" regarding directed graphs and not only regarding undirected graphs, so you understand better the concept. And what is better, the explanation uses a similar example like the one I draw in the question.

Here is the article:

http://www.brpreiss.com/books/opus4/html/page562.html

And what answer the question is that, in fact if you have a connected directed graph you don't necessary need to have a path between any two distinct vertices, that requirement is only if the graph is undirected.

I hope this 'auto-answer question' will help someone studying this same concept.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.