Нифонтова В.Н.
Владей своими страстями - или они овладеют тобою.
Исследования показали, что когда озвучиваешь два взаимоисключающих утверждения, как правило, люди задумываются.
Большая часть бед во всем мире происходит от того, что люди недостаточно точно понимают свои цели.
Иога́нн Во́льфганг фон Гёте
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.
Графы Эйлера
Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.
Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.
Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Решение.
Будем двигаться по схеме от первого города к последнему, последовательно находя количество путей из первого города в каждый следующий. Для этого нужно найти все города, из которых есть дороги в текущий, и сложить количества путей до этих городов от первого.
А = 1
Б =А = 1
Д = А + Б = 1 + 1 = 2
Г = Б = 1
В = Б + Г = 1 + 1 = 2
Ж = Д + Г = 2 + 1 = 3
Е = В + Г + Ж = 2 + 1 + 3 = 6
И = В + Е = 2 + 6 = 8
К = Е = 6
Л = И + Е + К = 8 + 6 + 6 = 20
Ответ: 20
Степени вершин и подсчет числа ребер графа.
Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.
С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин.
Для иллюстрации рассмотрим задачу.
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?
Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5.Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.
Ответ. Соединить телефоны таким образом невозможно.
Теорема: Любой граф содержит четное число нечетных вершин.
Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Связность графа
Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер.
Готовимся к зкзамену
