Графы

Основные определения

Граф G (V, E) — множество вершин (vertices, nodes, points) V и множество ребер E, такое, что

$$E\subseteq \{\{u,v\}:u,v\in V\}$$

является подмножеством множества двухэлементных подмножеств множества V (для неориентированного Undirected графа)

Ребро (Edge, links, lines)— неупорядоченная пара {u, v}, где u и v принадлежат V (для неориентированного графа)

x — ребро с концами u и v, {u, v}, тогда x инцидентно u и v и u и v инцидентны x Incident

Вершины u и v называются смежными, если являются концами одного ребра ребра x и y называются смежными, если имеют общую вершину

Ориентированный граф (орграф) G V, E Directed graph or Digraph — множество вершин V и ориентированных ребер E

$$E\subseteq \{(u,v):u,v\in V\}$$ $$E=R=\{(u,v):u,v\in V,u,v-\text{смежны}\}$$ $$E\subseteq V\times V;E\subseteq V^2$$

Ориентированное ребро (дуга) — упорядоченная пара (u, v), где u и v принадлежат V directed edges, directed links, directed lines, arrows or arcs

Направленный граф — граф без симметричных u, v и v, u пар ориентированных ребер Взвешенный граф G (V, E, w) — граф с весами на ребрах Weighted graph or a Network

Тривиальный граф — граф из одной вершины (1, 0) Trivial graph

Нуль граф — граф без ребер Edgeless graph

Пустой граф — граф без вершин Null or Empty graph

Двудольный граф — это граф, множество вершин которого можно так разбить на два непересекающихся подмножества (доли) $V_1$ и $V_2$ , что никакие две вершины из одной доли не смежны Bipartite graph or Bigraph

Кратные ребра (параллельные) Multiple edges — несколько ребер, соединяющие одни и те же две вершины

$$E=\{\{V_1,V_5\},\{V_1,V_5\},\{V_1,V_2\}$$

Петля Loop — ребро, соединяющее вершину саму с собой

$$v_{1}R{v}_2,R=\{(v_i,v_i):v_i,v_j\in V\text{и}{v}_i\text{и}{v}_j$$