2. Способы задания графов, свойства матриц смежности и инциденций, теорема о рукопожатиях.

Графом Gназывается пара (V,E), где– непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Способы представления графов:

• Текстовый

• Графический

• Матрицами

Определение. Матрицей смежностиn-вершинного графа называется квадратная матрицаразмераn, такая что

Матрица смежности любого графа обладает следующими свойствами:

• она симметрична относительно главной диагонали;

• на её главной диагонали стоят нули;

• сумма элементов i-й строки (i-го столбца) равнаdeg(v_i), т.е. количеству ребер, инцидентных вершинеv_i.

В матрице инциденций всегда выполнены следующие условия:

• сумма элементов любого её столбца равна двум;

• сумма элементов i-й строки равнаdeg(v_i).

Определение. Матрицей инциденцийn-вершинного графа сmребрами называется матрицаразмераnт, такая что

Утверждение. Для любого графаG= (V,E) сnвершинами иmребрами справедливо равенство т.е. сумма степеней всех вершин графа равна удвоенному количеству ребер.

Теорема о рукопожатиях – в любом графе число вершин нечетной степени четно (если кто-то с кем-то обменялся рукопожатием, число «пожатых рук» четно).