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

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

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

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

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

1	%%B, C%%
2	%%A, C%%
3	%%B, F%%
4	%%A, F%%
5	%%A, F%%
6	%%A, D%%
7	%%D, F%%
8	%%D, E%%
9	%%E, F%%
10	%%B, E%%
11	%%E, E%%

Матрицей инцидентности для графа %%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}$$

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

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