Дерево, эквивалентные определения — различия между версиями
| Строка 1: | Строка 1: | ||
| + | {{Определение | ||
| + | |definition = | ||
'''Дерево''' — неориентированный граф, в котором две любых вершины соединены единственным простым путем. Другими словами, любой связный граф без циклов дерево. | '''Дерево''' — неориентированный граф, в котором две любых вершины соединены единственным простым путем. Другими словами, любой связный граф без циклов дерево. | ||
| − | + | }} | |
| + | {{Определение | ||
| + | |definition = | ||
'''Лес''' {{---}} граф, являющийся набором непересекающихся деревьев. | '''Лес''' {{---}} граф, являющийся набором непересекающихся деревьев. | ||
| − | + | }} | |
==Определения== | ==Определения== | ||
Дерево - неориентированный простой граф G, который удовлетворяет любому из эквивалентных утверждений: | Дерево - неориентированный простой граф G, который удовлетворяет любому из эквивалентных утверждений: | ||
| − | + | # Любые две вершины графа G соединены единственным простым путем | |
| − | + | # G - связен и ацикличен | |
| − | + | # G - ацикличен, и простой цикл формируется при добавлении любого ребра | |
| − | + | # G - связен, и удаление любого ребра приводит к потере связности | |
==Доказательство эквивалентности== | ==Доказательство эквивалентности== | ||
Версия 03:59, 13 ноября 2011
| Определение: |
| Дерево — неориентированный граф, в котором две любых вершины соединены единственным простым путем. Другими словами, любой связный граф без циклов дерево. |
| Определение: |
| Лес — граф, являющийся набором непересекающихся деревьев. |
Определения
Дерево - неориентированный простой граф G, который удовлетворяет любому из эквивалентных утверждений:
- Любые две вершины графа G соединены единственным простым путем
- G - связен и ацикличен
- G - ацикличен, и простой цикл формируется при добавлении любого ребра
- G - связен, и удаление любого ребра приводит к потере связности
Доказательство эквивалентности
Литература
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
- Википедия — свободная энциклопедия
