Дерево, эквивалентные определения — различия между версиями
(→Доказательство эквивалентности) |
(→Доказательство эквивалентности) |
||
Строка 22: | Строка 22: | ||
* <tex> 2 \Rightarrow 3 </tex> Очевидно, граф связен. Докажем по индукции, соотношение <tex>p = q + 1</tex>. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает граф <tex> G </tex> несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точност две компоненты. По предположению индукции в каждой компоненте число вершин на еденицу больше числа ребер. Таким образом, <tex> q = p - 1 </tex> или <tex> p = q + 1 </tex>. | * <tex> 2 \Rightarrow 3 </tex> Очевидно, граф связен. Докажем по индукции, соотношение <tex>p = q + 1</tex>. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает граф <tex> G </tex> несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точност две компоненты. По предположению индукции в каждой компоненте число вершин на еденицу больше числа ребер. Таким образом, <tex> q = p - 1 </tex> или <tex> p = q + 1 </tex>. | ||
− | * <tex> 3 \Rightarrow 4 </tex> | + | * <tex> 3 \Rightarrow 4 </tex> Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавлеям ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию. |
==Литература== | ==Литература== |
Версия 21:14, 24 ноября 2011
Определение: |
Дерево — связный ациклический граф. |
Определение: |
Лес — граф, являющийся набором непересекающихся деревьев. |
Определения
Для графа G эвивалентны следущие утверждения:
- G - дерево
- Любые две вершины графа G соединены единственным простым путем
- G - связен и , где - количество вершин, а количество ребер
- G - ацикличен и , где - количество вершин, а количество ребер
- G - ацикличен и при добавлении любого ребра для несмежных вершин появляется цикл
- G - связный граф, отличный от для , а также при добавлении любого ребра для несмежных вершин появляется цикл
- G - граф, отличный от и , а также , где - количество вершин, а количество ребер, и при добавлении любого ребра для несмежных вершин появляется цикл
Доказательство эквивалентности
- Граф связен, значит любые две вершнины соединены путем, ацикличен, значит путь единственен, а так же прост, так как никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.
- Очевидно, граф связен. Докажем по индукции, соотношение . Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше вершин. Если же граф имеет вершин, то удаление из него любого ребра делает граф несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точност две компоненты. По предположению индукции в каждой компоненте число вершин на еденицу больше числа ребер. Таким образом, или .
- Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавлеям ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию.
Литература
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
- Википедия — свободная энциклопедия