CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
Steve
Steve

Reputation: 31

Can there be self loops for undirected graphs?

I mean directed graphs can have a self-loop, so I don't see the reason why an undirected graph cannot have it (CLRS says it's forbidden without giving a valid reason). 

Example: 

G_directed = (V,E) is a directed graph

Say this graph has the vertex set V = {1,2,3,4,5,6}

With edges E = {(1,2),(2,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)}
-----------------------------------------------------------------
Say we now decide to turn G_directed into an undirected graph:

G_undirected = (Vu,Eu) is an undirected graph

Vu = {1,2,3,4,5,6}

With edges E = {(1,2),(2,2),(2,4),(2,5),(4,1),(4,5),(6,3)}

In the example (2,2) is the self loop. I seriously don't see any problems this can have with graph traversals.

Upvotes: 3

Views: 9197

Answers (1)

trincot
trincot

Reputation: 350750

There are several categories of undirected graphs. Where loops (self references) are not allowed, they are called simple graphs. But there is indeed no reason to consider undirected graphs with loops and even multiple edges between the same pair of nodes: these are called multigraphs:

A loop is an edge (directed or undirected) that connects a vertex to itself; it may be permitted or not, according to the application.

A multigraph, as opposed to a simple graph, is an undirected graph in which multiple edges (and sometimes loops) are allowed.

Upvotes: 4

Related Questions