TransWikia.com

What is the difference between a semiconnected graph and a weakly connected graph?

Mathematics Asked by Maximilian Levine on December 20, 2021

These are the definitions I have found:

Semiconnected: if, and only if, for any pair of nodes, either one is reachable from the other, or they are mutually reachable.

Weakly connected: if, and only if, the graph is connected when the direction of the edge between nodes is ignored.

As far as I can tell, these definitions are identical.

2 Answers

$$bulletlongleftarrowbulletlongrightarrowbullet$$

From those definitions, the above diagram is weakly connected, but not semi connected, as you cannot get from either end node to the other, following the directions of arrows.

Answered by tkf on December 20, 2021

Semiconnected means that for every pair of vertices $(x,y)$, either there exists a path from $x$ to $y$ or a path from $y$ to $x$, with all steps of the path obeying the directionality of edges.

Weakly connected means that if you replace all the directed edges with undirected edges then the resulting undirected graph is connected.

Semiconnected implies weakly connected. The converse is not true, for example the graph $A rightarrow B leftarrow C$ is weakly connected but not semiconnected, because there is no path between $A$ and $C$ in either direction obeying the directionality of the edges. But if you forget about the directionality entirely then the graph becomes just $A leftrightarrow B leftrightarrow C$ which is definitely connected.

Answered by Ian on December 20, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP