Определениее графа.Основ.хар-ки.виды графов

Граф-это мн-во точек, наз. вершинами и мн-во линий называемых ребрами, кот-ые соединяют пары вершин или вершину саму с собой.

Опр1: Ненаправленный граф G- это конечное мн-во V-вершин и конеч. мн-во E-ребер и фун-я такая что, для каждого ребра Е отбражение есть одно или 2хэлементнное подмн. мн-ва V.

Опр2: 1) Пара вершин v и w назыв. смежными если ребро e, соединяющее их. В этом случае также говорят,что вершины v и w инцидентны ребру e и наоборот. 2) Ребра наз-ся смеж-ми если имеют по крайней мере одну общ. вершину. 3) Валентностью или степенью вершины v, наз. deg(V) число ребер инцидентных вершине (V) (петля учитывается дважды) ) Граф, у которого кажд. вершина имеет одинак. валентность r наз-ся правильным или r-валентным графом.

Опр3: 1) Нулевым графом или полностью несвяз. графом наз-ся граф с пустым мн-вом ребер. 2) Полным графом наз. граф у которого каждая пара вершин (различ-х) связана ровно одним ребром, степень каждой вершины в графе , т.к. кажд. вершина связана с каждой из остальных (n-1) вершиной по средством одного ребра. Всего ребер в таком графе n(n-1)/2. 3) Двудольным графом наз-ся граф,у кот-го мн-во вершин имеет разбиение { }: каждое ребро связ. вершины с вершинами из . 4) Полный двудольный граф – это двуд. граф, у которого кажд. вершина из связана с кажд. вершиной из одним ребром.( | |=n, | |=m) 5) Простой граф-это граф, кот-ый не имеет петель или кратных ребер.

Опр4: Пусть G граф со мн-вом вершин { }. Мат. смежности наз-ся эл. кот-ой числа различ. ребер, соед. вершины Vi,Vj, степень вершины Vi=сумме всех эл-ов i-ой строки (или i-ого столбца).

Опр5: Граф H наз-ся подграфом гр. G, если , ,