3 Начальные понятия теории графов Определение



Скачать 35.02 Kb.
Дата04.07.2013
Размер35.02 Kb.
ТипДокументы
3.1. Начальные понятия теории графов

Определение. Пусть и - конечные множества, ; - отображение множества в множество одно и двухэлементных подмножеств множества . Тройку называют неориентированным графом (или просто графом).

Элементы множества и называют соответственно вершинами и ребрами. Множество вершин и ребер графа будем также обозначать и . Отображение называют отображением инцидентности.

Пример 1. : , , , .

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

Если , где , то говорят, что ребро gif" name="object23" align=absmiddle width=12 height=15>соединяет вершины и . В этом случае будем писать . Если , то ребро называют петлей в вершине . В этом случае будем также писать и говорить, что соединяет вершину саму с собой.

Если - некоторое ребро данного графа, то вершины , называются смежными; говорят также, что , концевые вершины ребра .

Ребра и называются смежными, если они имеют общую концевую вершину.

Если - концевая вершина ребра , то ребро и вершина называются инцидентными.

Если и , то ребра и называются кратными. Число ребер, инцидентных вершине , (петля учитывается дважды) называется степенью вершины и обозначается .

Если , то вершина называется изолированной.

Если , то вершина называется висячей. Ребро, инцидентное висячей вершине, называется висячим.

Пример 2. Пусть , а . Отображение инцидентности задано следующим образом: , , , , , .

Для наглядности представим граф диаграммой.

Вершины , - концы ребра . Ребра , - кратные. Вершины и - смежные. Вершина инцидентна ребрам , , . , , , , . Вершина - висячая, ребро - висячее, вершина - изолированная.

Лемма (о рукопожатиях). Для любого графа сумма степеней вершин равна удвоенному числу ребер, т.е.

.

Доказательство. При подсчете суммы степеней вершин произвольное ребро внесет вклад, равный 1, как в степень вершины , так и в степень вершины , т.е. будет учтено в сумме дважды. ■

Следствие. В любом графе число вершин нечетной степени либо четно, либо равно 0.

Доказательство. Пусть и - соответственно множества вершин четной и нечетной степени. Тогда

.

Ясно, что первое слагаемое четно. Поэтому второе слагаемое либо также четно, либо равно нулю. В первом случае, так как во второй сумме все слагаемые нечетны, то их число четно. Следовательно, множество либо содержит четное число вершин, либо пусто. ■

Граф без петель и кратных ребер называется обыкновенным графом.

Будем называть граф одноэлементным, если он имеет единственную вершину. Граф называется нулевым, если множество его ребер пусто. Нулевой граф с вершинами будем обозначать

Обыкновенный граф называется полным графом, если любые его две различные вершины смежные. Для полного графа с вершинами применяется обозначение .

Пример 3.



Заметим, что степень каждой вершины полного графа равна , так что

.

Следовательно, число ребер полного графа с вершинами равно .

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

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

Полный двудольный граф с вершинами в одной доле и вершинами в другой () обозначают .

Пример 3.



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




Похожие:

3 Начальные понятия теории графов Определение iconI начальные понятия
Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936г., хотя начальные задачи теории графов...
3 Начальные понятия теории графов Определение iconVi. Элементы теории графов. Основные понятия теории графов. Определение Графом
Определение Графом называется совокупность 2-х множеств Х и У. Х это множество точек, называемых вершинами графа, а у это множество...
3 Начальные понятия теории графов Определение iconВопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры
Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры
3 Начальные понятия теории графов Определение iconЭлементы теории графов
...
3 Начальные понятия теории графов Определение iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
3 Начальные понятия теории графов Определение iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
3 Начальные понятия теории графов Определение iconОсновные понятия теории графов граф и его виды
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик...
3 Начальные понятия теории графов Определение iconОсновные понятия теории графов
Д. Кенига только в 1936 г., но многочисленные прикладные задачи и головоломки (которые, кстати, поддавались формулировкам в терминах...
3 Начальные понятия теории графов Определение iconЛекция 11: Графы и деревья
...
3 Начальные понятия теории графов Определение iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org