Лекции по дискретной математике. Глава 2. Часть 1 - файл n1.doc

Лекции по дискретной математике. Глава 2. Часть 1
скачать (1313.5 kb.)
Доступные файлы (1):
n1.doc1314kb.01.06.2012 12:06скачать

n1.doc

  1   2   3   4   5   6   7   8   9   10

Глава 2.

ПРОСТЫЕ ГРАФЫ (ГРАФЫ)




2.1. Способы задания графа


Основные способы задания графов:

2.1.1. Графический способ задания графа


Определения







На плоскости (в пространстве или на объемной фигуре) изображается некоторое количество точек (кружков) и какое-то число отрезков, кривых или ломаных линий соединяющих все, или некоторые из точек.

Кружки называются вершинами, а линии – ребрами, а полученная геометрическая фигура – ненаправленным графом (графом).

Замечание






Ребра показывают лишь связь между двумя вершинами, или ее отсутствие, однако направление этой связи (например, передача инфор­мации, сигналов, товаров, топлива, грузов и т.д.) в данной модели несущественно. Вот по­чему такие графы называются ненаправленными.



Ребро, соединяющее вершину саму с собой, называется петлей.

Несколько ребер, соединяющих две вершины, носят название кратных.

В зависимости от наличия или отсутствия петель и/или кратных ребер различают следующие типы ненаправленных графов:


Тип

Наличие кратных ребер

Наличие петель

Простой граф

Мультиграф

Псевдограф

Псевдомультиграф

Нет

Да

Нет

Да

Нет

Нет
Да

Да

Замечание





Далее будут рассматривать простые графы, которые будут кратко называться графами.


2

Определения

.1.2 Определение графа с помощью множеств



Множество называется поименованным, если каждому его элементу присвоено имя (метка, целое число).

В дальнейшем графом будет называться пара разделенных поименованных множеств G = (V,E) (V?E = ) и функция преобразования : (V)  Е.

Элементы множества V=V(G) являются вершинами графа G, а элементы множества E=E(G) – его ребрами. Функция преобразования устанавливает соответствие между именами ребер и неупорядоченными парами имен вершин. Поэтому ребра можно задавать как собственными именами, так и неупорядоченными парами имен вершин.

В дальнейшем для краткости записи функция преобразование  будет опускаться.


Определения






Граф 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 – некоторая вершина графа.

Вершина будет изолированной, если она не инцидентна ни с одним ребром.


Меры








2.1.3. Степени вершин графа


Определения







Степенью вершины графа ViV(G) (записывается как deg(Vi)) является число рёбер, смежных с вершиной Vi.

Изолированная вершина имеет deg(Vi)=0.

Очевидно, поскольку степень вершин задаёт число смежных вершин, deg(Vi)>0 для всех неизолированных вершин ViV(G). Если граф G имеет n вершин, то каждая вершина в графе максимально может иметь рёбра с другими n-1 вершинами (кроме ребра с самой собой, т.е. петли). Поэтому deg(Vi)n-l. От­сюда следует оценка для любого простого графа:
0 deg (Vi)  n-1

Меры





d(G) =

Лемма о рукопожатиях







Пусть G=(V,E) будет графом. Тогда

2E

Данное утверждение легко получить, если отметить, что в сумму степеней каждое реб­ро вносит 2 подсуммы: одну для вершины Vi, а вторую - для вершины Vj

Важно подчеркнуть, что лемма говорит о том, что степень всех вершин графа всегда четна.

2.1.4. Последовательность степеней вершин графа


Определения







Последовательностью степеней вершин графа G является последовательность его степеней, записанная в порядке возрастания степеней с повторами.

С помощью последовательности степеней графа можно задавать сам граф, но не всегда однозначно.


Определения







Последовательность d1,d2,…,dn неотрицательных целых чисел называется графической, если она представляет последовательность степеней графа.

Из леммы рукопожатий следует, что если последовательность неотрицательных чисел является графической, то сумма элементов в этой последовательности четна. Для простых графов наибольший элемент графической последовательности неотрицательных чисел равен n-1.

Теорема Havel - Hakimi






П

Замечания

оследовательность d1? d2? …?dn?0 неотрицательных целых чисел является графической тогда и только тогда, когда последовательность d2 –1, d3 – 1, …, dk+1, dk+2, dk+3,…,dn (k=d1) является графической.



1. Важно отметить, что описатели di являются только описателями последовательности. Запись последовательности в таком виде не означает, что вершины есть {1,2,..,n} и что d1 является степенью вершины 1 и т.д.

2. Теорема говорит, что если заданная последовательности является графической, то она может быть реализована в виде графа, в котором вершина степени d1 смежна с вершинами степени d2, d2,…, dk+1 (k= d1). Это утверждение задает правило построения графа по последовательности:

если был построен граф с n-1 вершинами и последовательностью степеней d2 –1, d3 – 1, …, dk+1, dk+2, dk+3,…,dn (k=d1), то добавляется новая вершина и соединяется с вершинами степени d2 –1, d3 – 1, …, dk+1-1, (k=d1).

  1   2   3   4   5   6   7   8   9   10


Глава 2. ПРОСТЫЕ ГРАФЫ (ГРАФЫ)
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации