8. Как находятся матрицы инцидентности и матрицы смежности?

Матрицы инцидентности и смежности:

Матрица инцидентности:

• Представляет собой таблицу, где строки соответствуют вершинам, а столбцы — рёбрам (или наоборот).
• Для неориентированного графа: элемент \( M_{ij} = 1 \), если вершина \( i \) инцидентна ребру \( j \), и \( 0 \) в противном случае. Если ребро является петлёй, значение может быть \( 2 \).
• Для ориентированного графа: \( M_{ij} = 1 \) если вершина \( i \) является началом дуги \( j \); \( -1 \) если вершина \( i \) является концом дуги \( j \); \( 0 \) в остальных случаях.

Матрица смежности:

• Представляет собой квадратную таблицу, где строки и столбцы соответствуют вершинам графа.
• Для неориентированного графа: элемент \( A_{ij} = 1 \), если существует ребро между вершинами \( i \) и \( j \), и \( 0 \) в противном случае.
• Для ориентированного графа: элемент \( A_{ij} = 1 \), если существует дуга из вершины \( i \) в вершину \( j \), и \( 0 \) в противном случае.
• Значения могут быть больше \( 1 \) для графов с кратными рёбрами или обозначать вес ребра.