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.

I'm studying graph theory and I'm facing the following question:

What happens when you have a connected graph with directed and undirected edges? Is it strongly connected or not?

With connected graph I'm saying that despite the 2 vertices of the graph you select, you can always find a path between them.

I was looking for the definition of strongly connected graph but I couldn't find if it is required that ALL the edges should be directed or not.

My thoughts are that if it's connected and you have at least one directed edge, then it is strongly connected, but I want to know if this is correct or not.

I reached to this conclusion because in the book I'm studying (Ralph Grimaldi - Discrete and Combinatorial Mathematics) when it defines what is a strongly directed graph, it show this graph:

http://i.imgur.com/C2Ece.png

And that's what I'm talking about, there are 4 directed edges and 1 undirected edge and the book call it a strongly connected graph.

Also and if this is true, then...

Do you have a directed graph when you have at least one directed edge on it or again... ALL the edges should be directed to call it a "Directed Graph"?

share|improve this question
    
Yes you are right, in fact I think I should replace every time I wrote vertices and put edges instead. Sorry for that, I'm not an English native speaker and I got confused. I've just corrected the question. –  mp19uy Nov 12 '12 at 13:44
add comment

2 Answers

up vote 4 down vote accepted

It depends on how you see undirected edges in presence of directed edges. Depending on your need, you can have your own definition of 'strongly connected' and define it accordingly.

As far as I know, if one says 'directed graph' then one usually means that all edges are directed. And if a graph is not directed, then it is undirected.

Here, you can also treat undirected edges as 'bi-directed' edges i.e. you can traverse in any direction on these edges. If you see undirected edges this way then yes, you can call a graph which has at least one directed edge, a 'directed graph'.

share|improve this answer
    
Before introducing strongly connected graphs, the book says that when you have a directed graph, if you have an edge without direction,then you consider it as a bi-directed edge. So it was like you said. Just for reference, this is from the book (Spanish Title: Matematicas Discreta y Combinatoria)(English Title: Discrete and Combinatorial Mathematics), Author: Ralph P. Grimaldi. The use of the undirected edges as bi-directed in directed graphs is explained at page (363/3Ed Spanish Ver.)(349/5Ed English Ver.) and the image I submitted is from page (366/3Ed Spanish Ver.)(352/5Ed English Ver.) –  mp19uy Nov 12 '12 at 14:39
add comment

[A directed graph] is connected if it contains a directed path from u to v or a directed path from v to u for every pair of vertices u, v. It is strongly connected or strong if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u, v. The strong components are the maximal strongly connected subgraphs. wikipedia

Just the reachability is relevant, not how it is implemented (via directed or undirected edges). Undirected edges can always be replaced by a pair of directed edges.

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.