Способы задания графов

Помимо геометрического (графического) и аналитического способов задания графов существует еще, как минимум, три эквивалентых им способа.

Матрицей смежности для графа $G = (V, E)$ называется квадратная матрица $A = (a_{ij})$, строкам и столбцам которой соответствуют вершины графа. Для неориентированного графа число $a_{ij}$ равно числу ребер, инцидентных $V_i$ и $V_j$. Для орграфа число $a_{ij}$ равно числу ребер с началом в $V_i$ и концом в $V_j$.

Списком ребер графа называется таблица, состоящая из двух столбцов, в которой на пересечении $i$-й строки и первого (левого) столбца записывается ребро $e_i$, а на пересечении $i$ -й строки и второго (правого) столбца записываются вершины, инцидентные ребру $e_i$.

Для того, чтобы список ребер однозначно задавал граф, необходимо помимо списка ребер указать множество всех изолированных вершин этого графа.

Матрицей инцидентности для графа $G = (V, E)$ называется матрица $B = (b_{ij})$, столбцам которой соответствуют вершины графа, а строкам — ребра. Число орграфа $b_{ij}$ равно: $$b_{ij} = \begin{cases} 1, \text{ если } e_j \text{ исходит из } V_i \\ -1, \text{ если } e_j \text{ заходит в } V_i \\ 0, \text{ если } e_j \text{ не инцидентно } V_i \end{cases}$$

Для неориентированного графа $b_{ij}$ равно: $$b_{ij} = \begin{cases} 1, \text{ если } e_j \text{ инцидентно } V_i \\ 0, \text{ если } e_j \text{ не инцидентно } V_i \end{cases}$$

У матрицы инцидентности есть пара особенностей:

• в каждой строке должны стоять две единицы, а все остальные символы — нули;
• она не используется для графов с петлями.