Специальность 230100.62 Контрольная работа по дискретной математике (стр. 6 )

Так для графа 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. Простым циклом может служить (, , , ), или (, , ) или (, , , ).

10. Граф G содержит n=9 вершин и m=11 рёбер. Чтобы получить дерево, покрывающее граф (а дерево содержит рёбер на единицу меньше чем вершин, т. е. 8), удалим 11—8=3 ребра, входящие в циклы так, чтобы граф оставался связным, например: , , .

Получим дерево, покрывающее граф:

Можно получить и другие деревья, покрывающие граф G.

Пример. Дан орграф G.

1. Построить матрицу смежности вершин .

2. Построить матрицу инцидентности .

3. Проверить, является ли граф эйлеровым. Если да, построить эйлеров цикл

.

Решение. 1. В матрице смежности для ориентированного графа элемент равен количеству дуг с началом в вершине и концом в вершине . В частности, для графа G для i=1, 2, 4, , так как в вершине имеется петля . Элементы , так как вершины и соединены двумя противоположно направленными дугами. В остальных случаях .

 

2. В матрице инцидентности ориентированного графа G

В частности для матрицы инцидентности графа G , так как петля, инцидентная , , так как дуга не инцидентна , , так как -начало , а , так как — конец и так далее.

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

Здесь -количество дуг инцидентных , для которых является началом, а - количество дуг, инцидентных , для которых является концом.