русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


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


Определение. Граф 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, v1, 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

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

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

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

           
     
 
 


дерево лес.

 



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


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.136 сек.