|
Глава 2.Ненаправленные графы, часть 1. Простые графы (графы) Способы задания графа Основные способы задания графов графический
Глава 2. ПРОСТЫЕ ГРАФЫ (ГРАФЫ)
![](24055_html_m32bccb34.gif) Основные способы задания графов:
графический;
с помощью множеств;
последовательность степеней графа;
матричный;
битовые цепочки и таблицы инцидентности.
2.1.1. Графический способ задания графа Определения
![](24055_html_m5754ac3d.gif)
На плоскости (в пространстве или на объемной фигуре) изображается некоторое количество точек (кружков) и какое-то число отрезков, кривых или ломаных линий соединяющих все, или некоторые из точек.
Кружки называются вершинами, а линии – ребрами, а полученная геометрическая фигура – ненаправленным графом (графом).
Замечание
![](24055_html_7cc05b5c.gif)
Ребра показывают лишь связь между двумя вершинами, или ее отсутствие, однако направление этой связи (например, передача информации, сигналов, товаров, топлива, грузов и т.д.) в данной модели несущественно. Вот почему такие графы называются ненаправленными.
![](24055_html_54cd7a92.gif)
Ребро, соединяющее вершину саму с собой, называется петлей.
Несколько ребер, соединяющих две вершины, носят название кратных.
В зависимости от наличия или отсутствия петель и/или кратных ребер различают следующие типы ненаправленных графов:
-
Тип
| Наличие кратных ребер
| Наличие петель
| Простой граф
Мультиграф
Псевдограф
Псевдомультиграф
| Нет
Да
Нет
Да
| Нет
Нет Да
Да
| Замечание
![](24055_html_4c0512d9.gif)
Далее будут рассматривать простые графы, которые будут кратко называться графами.
![](24055_html_m451ccda8.gif)
2 Определения .1.2 Определение графа с помощью множеств ![](24055_html_m32bccb34.gif)
Множество называется поименованным, если каждому его элементу присвоено имя (метка, целое число).
В дальнейшем графом будет называться пара разделенных поименованных множеств G = (V,E) (V∩E = ) и функция преобразования : (V) Е.
Элементы множества V=V(G) являются вершинами графа G, а элементы множества E=E(G) – его ребрами. Функция преобразования устанавливает соответствие между именами ребер и неупорядоченными парами имен вершин. Поэтому ребра можно задавать как собственными именами, так и неупорядоченными парами имен вершин.
В дальнейшем для краткости записи функция преобразование будет опускаться.
![](24055_html_57b665b.gif)
Определения
![](24055_html_6d7ef1cc.gif)
Граф G=(V,E) называется пустым, если |V(G)|≠0 , |E(G)|=0.
Нулевой граф – это граф G=(V,E) с |V(G)|=0 и |E(G)|=0.
Две вершины Vi и Vk называются смежными, если существует ребро, соединяющее эти вершины.
Ребра являются смежными, если они опираются на общую вершину.
Вершина графа v и некоторое его ребро е называются инцидентными, если e={v,w} или e={w,v}, где w – некоторая вершина графа.
Вершина будет изолированной, если она не инцидентна ни с одним ребром.
![](24055_html_m786db7a9.gif)
Меры
![](24055_html_m29761b55.gif)
Порядок графа |G| - число вершин графа, |G|=|V|.
Размер графа ||G|| - число ребер графа, ||G||=|E|.
2.1.3. Степени вершин графа Определения
![](24055_html_m32bccb34.gif)
Степенью вершины графа Vi V(G) (записывается как deg(Vi)) является число рёбер, смежных с вершиной Vi.
Изолированная вершина имеет deg(Vi)=0.
Очевидно, поскольку степень вершин задаёт число смежных вершин, deg(Vi)>0 для всех неизолированных вершин Vi V(G). Если граф G имеет n вершин, то каждая вершина в графе максимально может иметь рёбра с другими n-1 вершинами (кроме ребра с самой собой, т.е. петли). Поэтому deg(Vi) n-l. Отсюда следует оценка для любого простого графа: 0 deg (Vi) n-1
![](24055_html_m6139b2b7.gif)
Меры
![](24055_html_m4ab1ee9b.gif)
Степень вершины deg(Vi).
Минимальная степень графа δ(G)= min{deg(Vi) | Vi V}.
Максимальная степень графа Δ(G)= max{deg(Vi) | Vi V}.
Средняя степень графа
d(G) = ![](24055_html_m4925f96b.gif) ![](24055_html_49fa4b62.gif)
Лемма о рукопожатиях
![](24055_html_482d6e17.gif)
Пусть G=(V,E) будет графом. Тогда
2E
Данное утверждение легко получить, если отметить, что в сумму степеней каждое ребро вносит 2 подсуммы: одну для вершины Vi, а вторую - для вершины Vj
Важно подчеркнуть, что лемма говорит о том, что степень всех вершин графа всегда четна.
|
|
|