Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задание 2

ВЯТСКИЙ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

Кафедра информатики и вычислительной техники

Контрольная работа №1

Вариант №6

Предмет: Теория графов и сетей

Студент: 2 курса группы ивту-23

Ф.И.О.:Костанян Геворг Артушевич

Преподаватель: Т.В. Князькова

Киров

2015

Содержание

Задание 1. 3

Задание 2. 5

Задание 3. 6

Задание 4. 7

Задание 5. 10

Задание 1

Построить граф G=(X,A), где Х={х_i}, i=1,2,...,6, A={a_i}, i=1,2,...,11, a₁=(x₁,x₄), a₂=(x₂,x₃), a₃=(x₂,x₆), a₄=(x₃,x₅), a₅=(x₃,x₁), a₆=(x₄,x₅), a₇=(x₄,x₁), a₈=(x₅,x₁) a₉=(x₄,x₆), a₁₀=(x₆,x₁), a₁₁=(x₆,x₃).

1. Для графа G найти обратные многозначные отображения Г^-1(х₁), Г^-2(х₄) и т.д.

2. Подсчитать полустепени исхода и захода d₀(x₅) и d _t(x₅).

3. Построить матрицы смежности и инцидентности для графа G.

4. Найти прямое Т⁺(х₃) и обратное Т^-(х₆) транзитивные замыкания.

5. Построить порожденный подграф, включающий вершины x₁, x₂,x₄, x_6.

6. Построить остовный подграф, включающий дуги (x_i, x _j), если i+j> 4.

7. Найти все вершины, входящие в путь между вершинами (х₂ и х₃ ) и (х₂ и х₅).

Решение:

1. Обратным отображением 1-го порядка для вершины х_i является множество элементов x_j таких, что существует дуга (x_j, х_i), принадлежащая множеству дуг графа.

Для x₁ таковыми дугами являются a₅=(x₃,x₁), a₇=(x₄,x₁), a₈=(x₅,x₁), a₁₀=(x₆,x₁). Следовательно, Г^-1(х₁)={x₃, x₄, x₅, x₆,};

Для x₄ таковыми дугами являются a₁=(x₁,x₄). Следовательно, Г^-1(х₄)={x₁}.

2. Полустепенью исхода вершины х_i - d₀(х_i) называется количество дуг, исходящих из этой вершины. Т.о., d₀(x₅) = 1.

Полустепенью захода вершины х_i - d_t(х_i) называется количество дуг, входящих в эту вершину. Т.о., d _t(x₅) = 2.

3. Матрица смежности графа - это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.

В каждой ячейки матрицы инцидентности неориентированного графа стоит 0 или 1, а в случае ориентированного графа, вносятся 1, 0 или -1.

4. Прямым транзитивным замыканием некоторой вершины х_i – T+(х_i) является объединение самой вершины х_i с прямыми отображениями 1-го порядка, второго порядка и т.д.

Т⁺(х₃) = {x₃}U{x₁;x₅}U{x₄;x₁}U{x₅;x₁;x₆}U{x₁;x₃}={x₁; x₄; x₅; x₆}

Обратным транзитивным замыканием некоторой вершины х_i –T-(х_i) является объединение этой вершины с обратными отображениями 1-го, 2-го и т. д.

Т^-(х₆) = {x₆}U{x₂;x₄}U{x₁}U{x₃;x₄;x₅;x₆}={x₁; x₂; x₃; x₄; x₅; x₆}

5. Часть графа называется подграфом, порожденным множеством вершин, если его ребрами являются только те ребра множества, оба конца которых принадлежат.

Порожденный подграф, включающий вершины x₁, x₂,x₄, x_6.:

i=1,2,4,6, a₁=(x₁,x₄), a₃=(x₂,x₆), a₇=(x₄,x₁), a₉=(x₄,x₆), a₁₀=(x₆,x₁).

6. Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Остовный подграф, включающий дуги (x_i, x _j), если i+j> 4:

U=(X,A), где Х={х_i}, i=1,2,...,6, A={a_i}, a₁=(x₁,x₄), a₂=(x₂,x₃), a₃=(x₂,x₆), a₄=(x₃,x₅), a₆=(x₄,x₅), a₇=(x₄,x₁), a₈=(x₅,x₁) a₉=(x₄,x₆), a₁₀=(x₆,x₁), a₁₁=(x₆,x₃).

7. Все вершины, входящие в путь между вершинами (х2 и х3): путь прямой.

Все вершины, входящие в путь между вершинами (х2 и х5): x₂-x₃-x₅.

Задание 2

Построить граф G=(X,Г), где X={x_i}, i=1,2,...,6, Г (х₁)={х₂,х₄}, Г (х₂)={х₂,х₃,х₅}, Г (х₃)={х₃,х₆}, Г (х₄)={х₅}, Г (х₅)={х₂,х₅} Г (х₆)={х₁,х₃}.

1. Является ли он двудольным? Если нет, то какое минимальное число дуг необходимо убрать, чтобы он таковым стал?

2. Является ли граф антисимметрическим? Полным?

Решение:

1. Граф называется двудольным, если множество его вершин можно так разбить на два подмножества, чтобы концы каждого ребра принадлежали разным подмножествам.

Данный граф не является двудольным, т.к. существуют вершины, соединенные дугами с самими собой (цикл нечетной длины). Т.о., для того, чтобы сделать его двудольным – нужно убрать дуги из соединяющие вершину с самой собой. Далее, можно условно отбросить из рассмотрения вершины x4 и x5, т.к. цикл через них возможен только по цепочке x1-x4-x5-x2, что имеет такую же четность, что и переход x1-x2. Остается единственный цикл x1-x2-x3-x4-x1 (четная длина), а также x1-x4-x5-x2-x3-x6 (четная длина).

Можем сделать вывод о том, что граф без ребер вида xi-xi, т.е.

G=(X,Г), где X={x_i}, i=1,2,...,6, Г (х₁)={х₂,х₄}, Г (х₂)={х₃,х₅}, Г (х₃)={ х₆}, Г (х₄)={х₅}, Г (х₅)={х₂ } Г (х₆)={х₁,х₃} будет двудольным.

2. Антисимметричный граф - орграф, у которого отсутствует дуга из хi в xj, если существует дуга из xj в хi. В нашем случае существуют двунаправленные дуги, например x3-x6 или x2-x5. Следовательно, граф не является антисимметричным.

Граф называется полным, если любая пара вершин соединена одним ребром. В нашем случае вершины x5 и x6 не соединены вообще. Граф не является полным.