Ориентированные и неориентированные графы

• Граф — математическая структура, состоящая из множества вершин и набора соединений между ними.
• Вершина — элемент графа, представляющий объект или состояние.
• Ребро — связь между двумя вершинами в неориентированном графе.
• Дуга — упорядоченная пара вершин в ориентированном графе, где направление имеет значение.

Ориентированный граф (орграф) (англ. directed graph) — это граф, в котором каждому ребру присвоено направление. Формально орграф определяется как пара множеств ${\displaystyle G=(V,E)}$, где:

• ${\displaystyle V}$ — непустое множество вершин.
• ${\displaystyle E}$ — множество дуг, каждая из которых является упорядоченной парой элементов из ${\displaystyle V}$.

Дуга ${\displaystyle e=(u,v)}$ ведёт от начальной вершины ${\displaystyle u}$ к конечной вершине ${\displaystyle v}$. Отображения:

${\displaystyle \mathrm {init} :E\rightarrow V}$ — задаёт начало дуги.

${\displaystyle \mathrm {ter} :E\rightarrow V}$ — задаёт конец дуги.

Неориентированный граф — это граф, в котором рёбрам не присваивается направление. Он также определяется парой множеств ${\displaystyle G=(V,E)}$, где:

• ${\displaystyle V}$ — множество вершин.
• ${\displaystyle E}$ — множество рёбер, каждое из которых является неупорядоченной парой различных вершин из ${\displaystyle V}$.

Ребро ${\displaystyle e=\{u,v\}}$ соединяет вершины ${\displaystyle u}$ и ${\displaystyle v}$ без указания направления.

• В ориентированном графе связи между вершинами асимметричны: если есть дуга из ${\displaystyle u}$ в ${\displaystyle v}$, это не означает наличия дуги из ${\displaystyle v}$ в ${\displaystyle u}$.
• В неориентированном графе наличие ребра между ${\displaystyle u}$ и ${\displaystyle v}$ подразумевает связь в обоих направлениях.
• Матрица смежности ориентированного графа может быть несимметричной, тогда как для неориентированного графа она всегда симметрична.

• Ориентированные графы используются для моделирования процессов с направлением:

 * Сети дорог с односторонним движением.
 * Потоки данных или сигналов.
 * Диаграммы состояний в программировании и автоматике.

• Неориентированные графы применяются для представления взаимных связей:

 * Социальные сети, где дружба взаимна.
 * Электрические схемы без диодов.
 * Молекулярные структуры в химии.

Ориентированные и неориентированные графы являются фундаментальными инструментами в математике и информатике. Понимание их особенностей позволяет эффективно моделировать и анализировать различные системы и процессы, от сетей и схем до алгоритмов и структур данных.