Графы

1.

Графы
Определение. Графом называется геометрическая фигура,
состоящая из точек и соединяющих их линий. Точки называются
вершинами графа, а линии — ребрами.

2.

Графы
• Два ребра называются смежными, если они имеют общую
вершину.
• Два ребра называются кратными, если они соединяют одну и ту
же пару вершин.
• Ребро называется петлей, если его концы совпадают.
• Степенью вершины называют количество ребер, для которых
она является концевой (при этом петли считают дважды).
• Вершина называется изолированной, если она не является
концом ни для одного ребра.
• Вершина называется висячей, если из неё выходит ровно одно
ребро.

3.

Графы
Определение. Граф без кратных ребер и петель называется обыкновенным.
Пример 1.
В деревне 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был
соединен ровно с пятью другими?
Решение:
Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют
телефонам, а ребра — соединяющим их проводам. В этом графе 15 вершин, степень каждой из
которых равна пяти. Подсчитаем количество ребер в этом графе. Для этого сначала
просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено