Дерево, эквивалентные определения
| Определение: |
| Дерево (англ. tree) — связный ациклический граф. |
| Определение: |
| Лес (англ. forest) — граф, являющийся набором непересекающихся деревьев. |
Определения
Для графа эквивалентны следующие утверждения:
- — дерево.
- Любые две вершины графа соединены единственным простым путем.
- — связен и , где — количество вершин, а количество ребер.
- — ацикличен и , где — количество вершин, а количество ребер.
- — ацикличен и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
- — связный граф, отличный от для , а также при добавлении любого ребра для несмежных вершин появляется один простой цикл.
- — граф, отличный от и , а также , где — количество вершин, а количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
Доказательство эквивалентности
- Граф связен, поэтому любые две вершнины соединены путем. Граф ацикличен, значит путь единственен, а также прост, поскольку никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.
- Очевидно, что граф связен. Докажем по индукции, соотношение . Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше вершин. Если же граф имеет вершин, то удаление из него любого ребра делает граф несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, .
- Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавляем ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию.
- — ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то , где — число компонент связности. Поскольку , то , а значит — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.
- Поскольку для содержит простой цикл, то не может им являться. связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.
- Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку , получим . Любые две вершины соединены простой цепью, так как — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться , так как иначе добавив ребро, соединяющее две вершины цикла, мы получим более одного простого цикла, что противоречит условию. является собственным подграфом , поскольку не является для . — связен, а значит есть вершина смежная с . Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф является для , и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.
- Если имеет простой цикл, то он является отдельной компонентой по ранее доказанному. Все остальные компоненты должны быть деревьями, но для выполнения соотношения должно быть не более одной компоненты отличной от , так как в . Если это дерево содержит простой путь длины 2, то в можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является или . Значит является или , которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если ациклический и , то из и верно, что — связен. В итоге получаем, что является деревом по определению.
См. также
Источники информации
- Харари Ф. Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
- Википедия — дерево(теория графов)
