Основные понятия теории графов

Сентябрь 13, 2022

Главная
Математика
Основные понятия теории графов

Содержание

2. Топология – это раздел геометрии, изучающий свойства фигур, которые могут быть установлены без измерения и сравнения
3. Задача о семи мостах А С D В Можно ли обойти все Кенигсбергские мосты, проходя только
4. Свойства графов: Свойство 1: Число нечетных вершин графа всегда четно. Невозможно начертить граф, который имел бы
5. Свойства графов: Свойство 3: Граф только с двумя нечетными вершинами можно начертить одним росчерком, при этом
6. Задача о семи мостах А С D В Поскольку число нечетных вершин графа в задаче о
7. Фигура, которую можно начертить одним росчерком, называется уникурсальной фигурой. А такой граф, который можно начертить одним
8. Задача: Можно ли привязать к гвоздям А, В, С, Д, К, М веревку так, как показано
10. Скачать презентацию

Слайд 2

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

установлены без измерения и сравнения длин и величин углов, и которые имеют, тем не менее, геометрический характер.

Слайд 3

Задача о семи мостах
А
С
D
В
Можно ли обойти все Кенигсбергские мосты, проходя только

один раз через каждый из этих мостов?

Слайд 4

Свойства графов:
Свойство 1: Число нечетных вершин графа всегда четно. Невозможно начертить

граф, который имел бы нечетное число нечетных вершин.

Свойство 2: Если все вершины графа четные, то можно одним росчерком (т.е. без отрыва карандаша от бумаги, проводя по каждому ребру только один раз) начертить граф, при этом, движение можно начать с любой вершины и закончить в этой же вершине.

Слайд 5

Свойства графов:
Свойство 3: Граф только с двумя нечетными вершинами можно начертить

одним росчерком, при этом движение нужно начинать с одной из этих нечетных вершин и закончить в другой.

Свойство 4: Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

Слайд 6

Задача о семи мостах
А
С
D
В
Поскольку число нечетных вершин графа в задаче о

семи мостах оказалось равным 4, то такой граф нельзя начертить одним росчерком, а, следовательно, нельзя пройти по всем 7 мостам, побывав на каждом из них по одному разу и вернуться в начало пути.

Слайд 7

Фигура, которую можно начертить одним росчерком, называется уникурсальной
фигурой.
А

такой граф, который можно начертить одним росчерком, называю эйлеровым.

Слайд 8

Задача:
Можно ли привязать к гвоздям А, В, С, Д, К, М

веревку так, как показано на рисунке 5, не разрезая ее на части и не сдваивая?

Основные понятия теории графов

Содержание

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

Задача о семи мостахАСDВМожно ли обойти все Кенигсбергские мосты, проходя только

Свойства графов:Свойство 1: Число нечетных вершин графа всегда четно. Невозможно начертить

Свойства графов:Свойство 3: Граф только с двумя нечетными вершинами можно начертить

Задача о семи мостахАСDВПоскольку число нечетных вершин графа в задаче о

Фигура, которую можно начертить одним росчерком, называется уникурсальной фигурой. А

Задача:Можно ли привязать к гвоздям А, В, С, Д, К, М

Похожие презентации