Презентация Основные понятия теории графов. (Лекции 11-12) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Основные понятия теории графов. (Лекции 11-12) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 30 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Математика » Основные понятия теории графов. (Лекции 11-12)
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:30 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.25 MB
- Просмотров:95
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Граф G V,E состоит из двух](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img1.jpg)
Содержание слайда: Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами.
Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами.
№3 слайд
![Вершины vi и vj, определяющие](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img2.jpg)
Содержание слайда: Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek.
Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek.
Ребра с одинаковыми концевыми вершинами называются параллельными (e1,e4 ).
Петля– замкнутое ребро(e5).
Ребро, принадлежащее вершине, называется инцидентным (ребро e1 инцидентно вершинам v1 и v2).
№4 слайд
![Изолированная вершина не](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img3.jpg)
Содержание слайда: Изолированная вершина не инцидентна ни одному ребру (v3).
Изолированная вершина не инцидентна ни одному ребру (v3).
Две вершины смежны, если они являются концевыми вершинами некоторого ребра (v1, v4).
Если два ребра имеют общую концевую вершину, они называются смежными (e1, e2).
№19 слайд
![Маршрут в графе G V,E](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img18.jpg)
Содержание слайда: Маршрут в графе G=(V,E) — конечная чередующееся последовательность вершин и ребер v0, e1, v1, e2,…,vk-1, ek, vk, которая начинается и заканчивается на вершинах, причем vi-1 и vi являются концевыми вершинами ребра ei, 1 i k.
Маршрут в графе G=(V,E) — конечная чередующееся последовательность вершин и ребер v0, e1, v1, e2,…,vk-1, ek, vk, которая начинается и заканчивается на вершинах, причем vi-1 и vi являются концевыми вершинами ребра ei, 1 i k.
№20 слайд
![Маршрут называется открытым,](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img19.jpg)
Содержание слайда: Маршрут называется открытым, если его концевые вершины различны (v1, e1, v2, e2, v3, e3, v6, e9, v5, e7, v3, e11, v6).
Маршрут называется открытым, если его концевые вершины различны (v1, e1, v2, e2, v3, e3, v6, e9, v5, e7, v3, e11, v6).
Маршрут называется замкнутым, если его концевые вершины совпадают (v1, e1, v2, e2, v3, e7, v5, e3, v2, e4, v4, e5, v1).
№21 слайд
![Маршрут называется цепью,](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img20.jpg)
Содержание слайда: Маршрут называется цепью, если все его ребра различны.
Маршрут называется цепью, если все его ребра различны.
Цепь называется простой, если ее концевые вершины различны(v1, e1, v2, e2, v3, e8, v6, e11, v3).
Цепь называется замкнутой, если ее концевые вершины совпадают (v1,e1,v2,e2,v3,e7,v5,e3,v2,e4,v4,e5,v1).
№22 слайд
![Открытая цепь называется](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img21.jpg)
Содержание слайда: Открытая цепь называется путем, если все ее вершины различны (v1, e1, v2, e2, v3).
Открытая цепь называется путем, если все ее вершины различны (v1, e1, v2, e2, v3).
Цикл – это замкнутая цепь ( простой цикл, если цепь простая) (v1,e1,v2,e3,v5,e6,v4,e5,v1).
Число ребер в пути называется длиной пути. Аналогично определяется длина цикла.
№23 слайд
![. Степень каждой неконцевой](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img22.jpg)
Содержание слайда: 1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1.
1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1.
2. Каждая вершина цикла имеет степень 2 или другую четную степень. Обращение этого утверждения, а именно то, что ребра подграфа, в котором каждая вершина имеет четную степень, образуют цикл, — неверно.
3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин.
№24 слайд
![Две вершины vi и vj](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img23.jpg)
Содержание слайда: Две вершины vi и vj называются связанными в графе G, если в нем существует путь vi—vj. Вершина связана сама с собой.
Две вершины vi и vj называются связанными в графе G, если в нем существует путь vi—vj. Вершина связана сама с собой.
Граф называется связным, если в нем существует путь между каждой парой вершин.
Компонента связности – максимальный связный подграф в графе.
№25 слайд
![Степенью deg vj вершины vj](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img24.jpg)
Содержание слайда: Степенью deg(vj) вершины vj называется число инцидентных ей ребер, т. е. вершин в ее окружении.
Степенью deg(vj) вершины vj называется число инцидентных ей ребер, т. е. вершин в ее окружении.
Максимальная и минимальная степени вершин графа G обозначаются символами (G) и (G) соответственно:
(G)= (G)=
Граф G=(V,E) называется регулярным или однородным (степени r), если степени всех его вершин одинаковы. Степенью регулярного графа называется степень его вершин.
№26 слайд
![Утверждение лемма о](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img25.jpg)
Содержание слайда: Утверждение («лемма о рукопожатиях»)
Утверждение («лемма о рукопожатиях»)
Сумма всех вершин графа – четное число, равное удвоенному числу ребер:
Интерпретация леммы: поскольку в каждом рукопожатии участвуют две руки,то при любом числе рукопожатий общее число пожатых рук четно (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала).
Следствие
В любом графе число вершин нечетной степени четно
№27 слайд
![Два графа G и G изоморфны,](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img26.jpg)
Содержание слайда: Два графа G1 и G2 изоморфны, если существует такое взаимно-однозначное отображение между множествами их вершин и ребер, что соответствующие ребра графов G1 и G2 инцидентны соответствующим вершинам этих графов.
Два графа G1 и G2 изоморфны, если существует такое взаимно-однозначное отображение между множествами их вершин и ребер, что соответствующие ребра графов G1 и G2 инцидентны соответствующим вершинам этих графов.
Если граф G изоморфен геометрическому графу G' в Rn, то G' называется геометрической реализацией графа G в пространстве Rn.
№30 слайд
![Граф порядка n называется](/documents_6/a7ceeb5eedf6082acf85287e1668da6d/img29.jpg)
Содержание слайда: Граф порядка n называется помеченным, если его вершинам присвоены некоторые метки (например номера 1, 2, …, n).
Граф порядка n называется помеченным, если его вершинам присвоены некоторые метки (например номера 1, 2, …, n).
Абстрактный (или непомеченный) граф – это класс изоморфных графов.
Скачать все slide презентации Основные понятия теории графов. (Лекции 11-12) одним архивом:
Похожие презентации
-
Задачи, приводящие к теории графов. Основные понятия и определения. (Лекция 13)
-
Основные понятия теории вероятности. Лекция 1
-
Дискретные структуы. Теория графов. Основные понятия
-
Теория надежности. Основные понятия и определения. (Лекция 1)
-
Основные понятия и основные законы теории вероятностей (Лекция 3)
-
Лекция 1. Основные понятия теории вероятности
-
Дискретная математика. Основные понятия теории множеств. (Лекция 1. 1)
-
Основные понятия теории вероятности. Урок 1
-
Основные сведения из теории вероятностей. Лекция 1
-
Теория игр. Основные понятия