304
правки
Изменения
→Определения
* G - ацикличен, и простой цикл формируется при добавлении любого ребра
* G - связен, и удаление любого ребра приводит к потере связности
* G - связен, и полный 3-х вершинный граф не является его минором Для примера докажем эквивалентность первых четырёх утверждений. <tex>1 \Rightarrow 2</tex> Поскольку <tex>G</tex> связный граф, то любые две его вершины соединены простой цепью. Пусть <tex>P_1</tex> и <tex>P_2</tex> - две различные простые цепи, соединяющие вершины <tex>u</tex> и <tex>v</tex>, и пусть <tex>w</tex> - первая вершина, принадлежащая <tex>P_1</tex> (при переходе по <tex>P_1</tex> из <tex>u</tex> в <tex>v</tex>), такая, что <tex>w</tex> принадлежит и <tex>P_1</tex> и <tex>P_2</tex>, но вершина, предшествующая ей в <tex>P_1</tex>, не принадлежит <tex>P_2</tex>. Если <tex>w'</tex> - следующая за <tex>w</tex> вершина в <tex>P_1</tex>, принадлежащая также <tex>P_2</tex>, то сегменты (части) цепей <tex>P_1</tex> и <tex>P_2</tex>, находящиеся между вершинами <tex>w</tex> и <tex>w'</tex>, образуют простой цикл в графе <tex>G</tex>. Поэтому если <tex>G</tex> - ациклический граф, то между любыми двумя его вершинами существует самое большое одна цепь. <tex>2 \Rightarrow 3</tex> Ясно, что граф <tex>G</tex> - связный. Соотношение <tex>p = q + 1</tex> докажем по индукции. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает его несвязным, в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, общее число ребер в графе <tex>G</tex> должно равняться <tex>p-1</tex>. <tex>3 \Rightarrow 4</tex> Предположим, что в графе <tex>G</tex> есть простой цикл длины <tex>n</tex>. Этот цикл содержит <tex>n</tex> вершин и <tex>n</tex> ребер, а для любой из <tex>p - n</tex> вершин, не принадлежащих циклу,существует инцидентное ей ребро, которое лежит на геодезической , идущей от некоторой вершины цикла. Все такие ребра попарно различны; отсюда <tex>q \ge p</tex>, т. е. пришли к противоречию. <tex>4 \Rightarrow 1</tex> Предположим граф <tex>G</tex> имеет <tex>k</tex> компонент связности, и т. к. граф ациклический, то каждая компонента связности является деревом. Ввиду того, что <tex>1 \Rightarrow 3</tex> <tex>q = \sum \limits_{i = 1}^k (p_i - 1) = p - k</tex>, где <tex>p_i</tex> - количество вершин в <tex>i</tex>-й компоненте связности. Учитывая, что <tex>p = q + 1</tex>, получаем, что <tex>k = 1</tex>, т. е. <tex>G</tex> - дерево.}}
==Литература==
