![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Теория графов берет свое начало в 1736г. с решения знаменитым математиком Эйлером задачи о кенигсбергских мостах. Жителей Кенигсберга заинтересовал вопрос, могут ли они, начав путь с одного участка суши, обойти все семь мостов Кенигсберга, посетив каждый из этих мостов однажды, и и вернуться в пункт старта, не переплыв реки.
Эйлер переформировал задачу, изобразив участки суши в виде вершин, а мосты сделала ребрами графа. Напомним, что цепь в графе называется Эйлерова, если она содержит все ребра ровно 1 раз.
В графе с более чем одной вершиной есть эйлеров цикл тогда и только тогда, когда этот цикл включает все вершины графа.
Задача Эйлера. Обладает ли данный граф эйлеровым циклом или цепью?
Теорема Эйлера 1. Связный граф обладает эйлеровым циклом тогда и только тогда, когда все его вершины имеют четную степень.
2. Связный граф обладает эйлеровой цепью тогда и только тогда, когда ровно две его вершины имеют нечетную степень.
Граф называется плоским, если он расположен на плоскости так, что его ребра не пересекаются, кроме как в вершинах.
Граф называется планарным, если его можно расположить на плоскости так, что ребра не будут пересекаться.
Гранью плоского графа называется часть плоскости, ограниченная ребрами и не содержащая в себе ни ребер, ни вершин.
Так как планарный граф можно превратить в плоский, то понятие грани имеет смысл и для него.
Пусть В – вершина графа, Г – грань, Р – ребро. Тогда справедлива следующая формула (формула Эйлера): Г+В-Р=2.
Дата публикования: 2015-10-09; Прочитано: 367 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!