Графы. Вершина. Ребро. Представление задачи с помощью графов.
Леонард Эйлер
(1707г – 1783гг)
Швейцарский, прусский и российский математик
Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.
Теория графов зародилась в ходе решения головоломок двести с лишним лет назад.
Задача о Кенигсбергских мостах
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.
Задача о Кенигсбергских мостах
Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.
Дальше
Задача о Кенигсбергских мостах
Пройти по Кенигсбергским мостам, при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия соблюдая заданные условия, нельзя.
дальше
Что такое граф
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними отрезками или дугами.
Примеры графов: карта дорог, схема метро, электросхема, чертеж прямоугольника и т.п.
Применение графов
Лабиринт - это граф. А исследовать его - это найти путь в этом графе.
дальше
Что такое граф
Графом называется конечное множество точек, некоторые из которых соединены линиями.
Точки называются вершинами графа, а соединяющие линии – рёбрами.
(Каждое ребро соединяет ровно две вершины).
Рёбра графа
Вершины графа
Е́сли в двух гра́фах верши́ны свя́заны рёбрами в одно́м и том же поря́дке, то таки́е гра́фы счита́ются одина́ковыми.
Степень вершин
Количество рёбер, которое выходит из вершины графа, называется степенью вершины (вале́нтностью).
Вершина графа, у которой нечётная степень, называется нечетной, а чётная степень степень – чётной.
Нечётная степень
(из вершины выходят три ребра)
Чётная степень
(из вершины выходят четыре ребра)
Теорема о сумме степеней вершин.
ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ТОЛЬКО ОДНИМ РЕБРОМ.
ДОПОЛНЕНИЕМ ГРАФА НАЗЫВАЕТСЯ ГРАФ С ТЕМИ ЖЕ ВЕРШИНАМИ И ИМЕЮЩИЙ ТЕ И ТОЛЬКО ТЕ РЕБРА, КОТОРЫЕ НЕОБХОДИМО ДОБАВИТЬ К ИСХОДНОМУ ГРАФУ, ЧТОБЫ ОН СТАЛ ПОЛНЫМ.
ДОПОЛНЕНИЕ ГРАФА ДО ГРАФА
Упражнения
1. В графе 3 вершины, каждая из которых имеет степень 2. Сколько у него ребер? Нарисуйте такой граф.
Ответ: 3.
2. В графе 4 вершин, каждая из которых имеет степень 3. Сколько у него ребер? Нарисуйте такой граф.
Ответ: 6.
3. В графе 5 вершин, каждая из которых имеет степень 4. Сколько у него ребер? Нарисуйте такой граф.
Ответ: 10.
П
И
А
М
С
В
Н
Д
Е
Ответ: нет.
№ 4.
Одноклассники Андрей, Борис, Вадим, Григорий, Дмитрий и Евгений устроили турнир по настольному теннису и решили играть каждый с каждым. Турнир еще не закончен. Ребра графа показывают, кто с кем играл к этому моменту.
Д
Е
А
Г
Б
В
№5.
Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Решение:
А
Г
В
Б
Д
1
2
3
4
5
6
7
8
9
10
Ответ: 10.
Аркадий
Борис
Владимир
Григорий
Дмитрий
Изобразим точками всех участников рукопожатий. Будем постепенно соединять точки отрезками-это «рукопожатия» и считать их количество.
№6.
В первенстве класса по настольному теннису принимали участие 5 учеников: Андрей, Борис, Галина, Олег, Елена.
Первенство проводилось по круговой системе – каждый участник играет с каждым из остальных один раз.
К настоящему моменту некоторые игры уже проведены:
Сколько игр проведено к настоящему
моменту и сколько ещё осталось?
Решение
Андрей
Борис
Галина
Елена
Олег
Ответ: сыграно 5 партий,
осталось 5 партий.
№7. По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвовали 4 человека?
1
2
3
4
Ответ: 12.
№8.
У Васи в альбоме нарисован прямоугольник, разделённый на три равные части. Он должен закрасить каждую из этих частей в один из трёх цветов: красный, жёлтый, зелёный. Нельзя закрашивать разные части одинаковым цветом. Сколько вариантов рисунка может получиться?
1 клетка
2 клетка
3 клетка
Ответ: 6 вариантов
№9. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Е?��
1
1
Отметим на рисунке индексами сверху каждого пункта количество путей,
с помощью которых в него можно попасть
1+1=2
2+1=3
2+1=3
3+3+2=8