Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Некоторые общие понятия теории графов.

Формулы алгебры высказываний. | Равносильность формул. | Совершенная дизъюнктивная нормальная форма. | Совершенная конъюнктивная нормальная форма. | Минимизация ДНФ. | Табличный способ задания. | Графический способ задания. | Логика предикатов. Кванторы. | Пример тождественно истинного предиката: . | Элементы теории графов. |


Читайте также:
  1. I. ОБЩИЕ ПОЛОЖЕНИЯ
  2. I. Общие требования
  3. I. ОБЩИЕ ТРЕБОВАНИЯ БЕЗОПАСНОСТИ
  4. I. Понятие и классификация ощущений, их значение в теории ПП. Роль восприятия в маркетинге
  5. II. Краткие сведения из теории
  6. II. Культурологическая мысль. Концепции (теории) культуры
  7. II. ОБЩИЕ ПОЛОЖЕНИЯ

Определение. Граф G,′ (V′, E′) называется подграфом графа G(V, E), если V′ .

Обозначение: Таким образом, каждая вершина в G′ является вершиной в G, и каждое ребро в G′ ребром в G.

v1 v2

 

 

v3 v4

неограф без петель подграфы первого графа.

 

Путь (маршрут в графе) – это совокупность ребер, которые объединены вместе вершинами так, что вдоль них можно двигаться по графу.

Определение.

Пусть G=G(V, E) – граф с вершинами v0, v1, v2,..., vk, V и ребрами e1, e2 e3,..., ek E. Маршрутом на неориентированном графе G называется последовательность v0, e1, v 1, e2, v2, e3,..., vk -1, ek, vk., где ei = {vi – 1, vi}.

v2

v1 e2 e3

 

e1 v3

e4

v0 v4

 

 

В дальнейшем маршрут будем обозначать через перечисление вершин.

Вершину v0 называют началом, а vk концом пути.
Если v0
= vk, то маршрут называют циклом. Маршрут, в котором все ребра попарно различны, называют простым циклом (нет повторяющихся ребер). Цикл, в котором попарно различны все его вершины (кроме начальной и конечной вершины), называется элементарным циклом.

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

Теорема (критерий эйлеровости графа). Для того, чтобы конечный связный граф был эйлеровым. необходимо и достаточно, чтобы степени всех его вершин были четными числами.

Докажем необходимость. Она очевидна, т. к. в каждую вершину мы входим по одной дуге, а выходим по другой. Такая пара дуг дает вклад, равный двум в степень вершины. А, поскольку эйлеров цикл содержит все вершины, то сумма степеней будет четным числом.

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

a

 

b c

       
 
   
 


d

Определение. Граф называется деревом, если он связен и не имеет циклов.

Определение. Несвязный неориентированный граф называется лесом.

Лес состоит из деревьев.

           
     
 
 


дерево лес.

 


Дата добавления: 2015-07-20; просмотров: 46 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Матрицы графов.| Взвешенные графы и алгоритмы поиска кратчайшего пути.

mybiblioteka.su - 2015-2024 год. (0.007 сек.)