- Множество объектов и соединяющих их попарно связей удобно изображать в виде графа. При этом узлы (вершины) графа – это объекты, а рёбра – связи.
- Степенью вершины называется количество выходящих из неё рёбер.
- Сумма степеней всех вершин графа равна удвоенному числу его рёбер.
- Путём в графе называется последовательность рёбер, в которой конец одного ребра служит началом следующего. Путь без повторов рёбер – это цепь.
- У связного графа любая пара вершин связана хотя бы одной цепью.
- Замкнутый путь, у которого начало и конец находятся в одной вершине, – это цикл.
- Дерево – это связный граф, не содержащий циклов. У дерева различают корень (первую вершину, из которой исходят все дуги) и листья (концевые вершины, из которых не выходит ни одна дуга).
- Между любыми двумя вершинами дерева существует единственный путь, который их соединяет.
Математика • 9 класс
521
Деревья и графы
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках