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

1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Якимчук Любовь Григорьевна
Преподаватель Технического колледжа

2.

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

3.

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

4. Свойства графов:

СВОЙСТВА ГРАФОВ:
Свойст во 1: Число нечет ных вершин графа всегда
чет но. Невозможно начерт ит ь граф, кот орый имел
бы нечет ное число нечет ных вершин.
Свойст во 2: Если все вершины графа чет ные, т о
можно одним росчерком (т .е. без от рыва карандаша
от бумаги, проводя по каждому ребру т олько один
раз) начерт ит ь граф, при эт ом, движение можно
начат ь с любой вершины и закончит ь в эт ой же
вершине.

5. Свойства графов:

СВОЙСТВА ГРАФОВ:
Свойст во
3:
Граф
т олько
с
двумя
нечет ными
вершинами можно начерт ит ь одним росчерком, при
эт ом движение нужно начинат ь с одной из эт их
нечет ных вершин и закончит ь в другой.
Свойст во 4: Граф с более чем двумя нечет ными
вершинами невозможно начерт ит ь одним росчерком.

6.

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

7.

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

8. Задача:

ЗАДАЧА:
.
Можно ли привязат ь к гвоздям А, В, С, Д,
К, М веревку т ак, как показано на рисунке
5, не разрезая ее на част и и не сдваивая?
В
С
Д
А
М
К

9. Какие из этих графов являются эйлеровыми?

КАКИЕ
ИЗ ЭТИХ ГРАФОВ ЯВЛЯЮТСЯ
ЭЙЛЕРОВЫМИ?