Упражнения. 1. В графе число вершин нечётной степени чётно

1. В графе число вершин нечётной степени чётно. Докажите это.

2. Докажите, что в любом графе, содержащем не менее двух вершин, найдутся две вершины одинаковой степени.

3. Можно ли 7 человек соединить телефонной связью таким образом, что каждый из них связан ровно с тремя другими?

5.2. Способы задания графа

Задать граф – описать множества его вершин и рёбер, а также отношения инцидентности. Для описания конечных графов достаточно перенумеровать вершины и рёбра.

Способ 1. Пусть – вершины графа G, x ₁, …, x_h – рёбра. Отношение инцидентности можно определить матрицей инцидентности , имеющей h строк и n столбцов. Если ребро x инцидентно вершине , то = 1, в противном случае = 0. В матрице инцидентности ориентированного графа G, если вершина – начало ребра x_i, то = -1, а если конец ребра, то +1. Если x_i – петля, а – инцидентная ей вершина, то , где – любое число, отличное от 1, 0, -1. В остальных случаях = 0.

Способ 2. Отношение инцидентности можно задать списком рёбер графа. Каждая строка этого списка соответствует ребру, а в ней записаны номера вершин, этому ребру инцидентных.

Способ 3. В матрице смежности графа столбцам и строкам соответствуют вершины графа. Элемент этой матрицы равен количеству рёбер, инцидентных i- й и j- й вершинам, если в графе допускаются кратные рёбра. Для ориентированного графа этот элемент равен количеству рёбер с началом в вершине i и концом в вершине j.