Сформулируем некоторые закономерности, присущие определенным графам:
1) Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
2) Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива для любого графа.
3) Если степени всех вершин графа равны, то граф называется однородным.
4) Число нечетных вершин любого графа четно.
5) Невозможно начертить граф с нечетным числом нечетных вершин.
6) Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проведя по каждому ребру только один раз, начертить этот граф, причем движение можно начать с любой вершины. Такой граф называется уникурсальным.
7) Граф, имеющий две нечетные вершины, можно начертить, не отрывая карандаша от бумаги, начав движение с одной из нечетных вершин.
8) Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.
Разберем еще некоторые понятия, необходимые для решения задач, используя графы.
Путем в графе от одной вершины до другой называется такая последовательность ребер, соединяющих вершины, что никакое ребро при движении не повторяется дважды.
Циклом называется путь, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется эйлеровой линией.
Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет, то граф несвязный.
Деревом называется любой связный граф, не имеющий циклов. Для каждой пары вершин дерева существует единственный путь, их соединяющий (рис.7).
Рис 7
Рассмотрим задачу, которую легко можно решить, используя теорию графов.
ЗАДАЧА. Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?
Do'stlaringiz bilan baham: |
