\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Directed Graphs
Undirected Graphs
Needed by:
Sheet PDF
Graph PDF

Directed Graph Skeletons


The skeleton of the directed graph $(V, E)$ is the undirected graph $(V, F)$ where

\[ F = \Set*{\set{v, w} \subset V}{(v, w) \in E \text{ or } (w, v) \in E}. \]

In other words, the skeleton is an undirected graph whose vertex set is $V$ and whose edges are all (unordered) pairs which appear as an ordered pair in the directed graph.

In the case that $(V, E)$ is a directed graph and $E$ is a symmetric relation, the skeleton of $(V, E)$ is a natural undirected graph to associate with $(V, E)$. An orientation of an undirected graph $G$ is a directed graph whose skeleton is $G$.

An oriented graph is a directed graph without self-loops satisfying the property for any two vertices $x$ and $y$, either $(x,y)$ or $(y,x)$ is an edge, but not both. An oriented graph can be obtained from an undirected graph by selecting an “orientation” of the undirected edges.

Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view