Теорема о связанном графе
k-edge -связный граф - k-edge-connected graph
В самом общем смысле граф — это множество точек вершин , узлов , которые соединяются множеством линий рёбер, дуг [1]. Теория графов то есть систем линий, соединяющих заданные точки включена в учебные программы для начинающих математиков, поскольку [2] [3] [4] [5] :. На протяжении более сотни лет развитие теории графов определялось в основном проблемой четырёх красок. Решение этой задачи в году оказалось поворотным моментом истории теории графов, после которого произошло её развитие как основы современной прикладной математики. Универсальность графов незаменима при проектировании и анализе коммуникационных сетей [7].
Пусть G — орграф. Вершина v 0 называется началом , v k — концом маршрута, а число k — длиной маршрута. Мы будем говорить, что маршрут e 1 ,e 2 ,…,e k проходит через дуги e 1 ,…,e k и вершины v 0 ,v 1 ,…,v k. Так как рассматриваются орграфы без петель и кратных дуг, то последовательность вершин v 0 ,v 1 ,…,v k однозначно определяет маршрут e 1 ,…,e k. Этим фактом мы будем иногда пользоваться при задании маршрута.
- Доказательство теоремы
- В математике и информатике , связность является одним из основных понятий теории графов : он запрашивает минимальное количество элементов узлов или ребер , которые необходимо удалить, чтобы разделить оставшиеся узлы на изолированные подграфы. Это тесно связано с теорией проблем сетевого потока.
- Доказательство того, что в любом графе сумма степеней вершин равна двойному числу ребер, является одним из фундаментальных результатов в теории графов.
- Теорема Грёча — утверждение, что любой планарный граф без треугольников может быть раскрашен в три цвета. Согласно теореме о четырёх красках , для любого графа, который может быть нарисован на плоскости без пересечения рёбер, можно раскрасить его вершины не более чем в четыре различных цвета так, что любые два конца любого ребра имеют различные цвета.
- Определения и свойства связности в графах
- Теорема Куратовского сильнее теоремы Вагнера — гомеоморфный подграф может быть преобразован в минор того же типа путём стягивания всех, кроме одного, рёбер в каждом пути, полученном при разбиении ребра путем добавления вершины, а вот обратное преобразование из минора в гомеоморфный подграф того же типа не всегда возможно. Миноры графов часто изучаются в более общем контексте миноров графовых матроидов.
- Доказать, что а из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево; б в дереве с n вершинами ровно n — 1 ребро; в в дереве не меньше двух висячих вершин; г в связном графа из n вершин не меньше n — 1 ребра; д если в связном графе n вершин и n — 1 ребро, то он — дерево.
- В теории графов связанный граф является k-реберно-связанным, если он остается связанным , когда удаляется менее k ребер.
Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два помечаем уже пройденые ребра , если эта вершина не является стартовой она же конечная для цикла. Для стартовой конечной вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может.
