Ориентированные и неориентированные графы

Практические задания

Задание 1

Пусть A={0,1,2,:10}, B={E0,E1, ...E10}, где E0=(0), E1=(0,1), E2=(0,2), E3=(0,3), E4=(1,4), E5=(1,5), E6=(1,6), E7=(3,7), E8=(3,8), E9=(4,9), E10=(4,10). Построить и определить граф.

Задание 2

Для графа, показанного на рисунке 1 описать подграф, порожденный вершинами {х1, х2, x3, x4};


Рисунок 1

Задание 3

Доказать, что если A - матрица инцидентности простого неориентированного графа без петель, то его матрица смежности получается из A.AT(mod 2) путем замены всех элементов на диагонали нулями (AT - матрица, получаемая транспонированием матрицы A).

Задание 4

Охарактеризуйте матрицу смежности:

  1. полного графа на n вершинах;
  2. двудольного графа.

Задание 5

    Задать графы G2 - G3 (см. рис. 2) множествами их вершин и ребер. Сравнить графы G1 - G3.

    Рисунок 2

    Задание 6

    Определить дополнение ┐G графа G, если:

    1. G - Пятиугольник;
    2. G - Треугольник.

    Какой ориентированный граф канонически соответствует графу G (представить графически)?

    Задание 7

    Задать графы G1 - G3, изображенные на рисунке 2, матрицами инцидентности и смежности, а также списком ребер.