Матрица смежности. Матрица инциденций. Численные характеристики графов. Плоские графы

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

Есть два стандартных способа представить граф G = (V,E) 

• 
  – как набор списков смежных вершин
  
• 
  как матрицу смежности.
  

Первый обычно предпочтительнее, ибо дает более компактное представление разреженных графов– тех, у которых |E| много меньше |V|².

Большинство стандартных алгоритмов используют именно это представление. Но в некоторых ситуациях удобнее пользоваться матрицей смежности – например, для плотных графов, у которых |EG| сравнимо с |VG|².

Матрица смежности позволяет быстро определить, соединены ли две данные вершины ребром. Алгоритмы отыскания кратчайших путей для всех пар вершин, используют представление графа с помощью матрицы смежности.

• 
  Определение Матрицей смежностиграфа G = (V, E) называется квадратная булева матрицаAпорядкаn,элементы которой определяются следующим образом:
  

Свойства

1. 
   А – симметрическая матрица
   
2. 
   На главной диагонали матрицы смежности всегда стоят 0.
   
3. 
   Число единиц в строке равно степени соответствующей вершины.
   

Матрицей инцидентностиграфаGназывается булева матрица размера |V|´|G| вида



Свойства:

1. 
     В каждом столбце матрицы ровно две единицы
   
2. 
   Равных столбцов нет.
   

Например, на следующем рисунке граф задан графически, списком смежных вершин, матрицей смежности и матрицей инцидентности.

графически	список смежных вершин     номер вершины степень вершины         1 2 2 5     2 4 1 3 4 5 3 2 2 4     4 3 2 3 5   5 3 1 2 4
матрица смежности   1 2 3 4 5 1 0 1 0 0 1 2 1 0 1 1 1 3 0 1 0 1 0 4 0 1 1 0 1 5 1 1 0 1 0	матрица инцидентности   e1 e2 e3 e4 e5 e6 e7 1 1 1 0 0 0 0 0 2 0 1 1 0 1 1 0 3 0 0 0 0 0 1 1 4 0 0 0 1 1 0 1 5 1 0 1 1 0 0 0

Рассматриваются также графы с нагруженными ребрами или взвешенные – графы, у которых каждому ребру поставлено в соответствие некоторое вещественное число – вес или нагрузка ребра.

Такой граф можно задать матрицей расстояний – квадратной матрицей размера |V|´|V|, где на пересечении i-ой строки и j-го столбца записан вес ребра (i, j), если ребро есть, ¥, если ребра нет и 0, если i = j.