7
$\begingroup$

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"?

Improve this question
$\endgroup$
5
$\begingroup$

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'.

Improve this answer
$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – mp19uy Nov 12 '12 at 14:39
1
$\begingroup$

[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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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