1. Определить степени всех вершин графа.

2. Записать матрицу смежности вершин .

3. Записать матрицу инцидентности .

4. Указать мосты и точки сочленения, если они есть.

5. Проверить, является ли граф эйлеровым.

6. Проверить, является ли граф гамильтоновым.

7. Проверить, является ли граф двудольным. Если да, указать подмножества V1 и V2.

8. Записать какой-нибудь маршрут от до .

9. Указать какой-нибудь простой цикл.

10. Построить дерево, покрывающее граф.

Решение. 1.Степенью вершины графа называется количество рёбер, инцидентных ей. Вершине инцидентно лишь одно ребро e1, значит, , а вершине инцидентны ребра , , , значит, и т. д. Составим таблицу.

1

3

2

2

4

3

3

3

1

2.Матрица смежности вершин.

, где — число вершин, равно количеству рёбер, соединяющих вершины и .

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

В нашем примере , так как нет петель, , так как вершина смежна , и т. д.

3.Матрица инцидентности имеет m строк (m-количество рёбер) и n столбцов, , если ребро инцидентно вершине , и в противном случае.

Так для графа G , так как ребро инцидентно вершине , , а .

,

.

4. В графе можно удалять рёбра и вершины. Если удаляется ребро, то все вершины сохраняются, если же удаляется вершина, то удаляются все инцидентные ей рёбра. Вершина, при удалении которой число компонент связности увеличивается, называется точкой сочленения.

Ребро с таким свойством называется мостом.

В графе G точками сочленения являются вершины Действительно, при удалении вершины связный граф G превращается в две компоненты,


так как удаляются рёбра , , . Аналогично при удалении получается вершина и связный граф.

При удалении получим


Мостами являются рёбра и .

5. Необходимым и достаточным условием эйлеровости графа является его связность и четность степеней всех вершин. Так как в графе G есть вершины степени 3 и 1, то он не является эйлеровым.

6. Критерия гамильтоновости графа не существует. Однако при наличии висячих вершин (вершин степени 1), мостов или точек сочленения граф гамильтоновым не будет. В графе G есть и висячие вершины, и мосты, и точки сочленения. Следовательно, граф не является гамильтоновым.

7. Необходимым и достаточным условием двудольности графа является отсутствие в нём циклов нечётной длины. В графе G есть циклы длины 3: и . Следовательно, граф G не является двудольным.

Если бы нам был дан граф G1,
полученный из G удалением ребра e8, то он был бы двудольным. В G1 ко множеству V1 отнесём вершину обведём её кружочком, смежную с ней вершину отнесём ко множеству V2, смежные вершины и , отнесём к V1 и обведём кружочком и т. д. Данный двудольный граф удобно изобразить иначе, выделяя множества V1 и V2.


8. Маршрутом от v1 до v9 в графе G может служить последовательность рёбер: (, , , , , , ).

9. Простым циклом может служить (, , , ), или (, , ) или (, , , ).

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15