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

Примеры решения задач. Пример 1. Пусть задан граф G, показанный на рис

Читайте также:
  1. B. Принятия оптимального управленческого решения по наиболее важным вопросам деятельности на рынке.
  2. I. 1.1. Пример разработки модели задачи технического контроля.
  3. I. 3.1. Двойственная задача линейного программирования.
  4. I.2. Структура оптимизационных задач
  5. I.5.3. Подготовка данных для задачи линейного программирования.
  6. I.5.4. Решение задачи линейного программирования.
  7. I.5.5. Просмотр и анализ результатов решения задачи.

Пример 1. Пусть задан граф G, показанный на рис. 15.23. Подсчитать количество маршрутов длиной 3 в данном графе.

Решение: Запишем матрицу смежности графа G:

.

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

r 2 ij = aik bki,

где r 2 ij ─ элемент матрицы R2.

Вычислив, таким образом, значения всех элементов, мы придем в итоге к следующей матрице:

.

Для того, чтобы определить количество маршрутов длиной 3 в исходном графе, необходимо полученную на первом шаге матрицу R2 умножить на R. Например,

r 31,2 = r 1,1 r 21,2 + r 1,2 r 22,2 + r 1,3 r 23,2 + r 1,4 r 24,2 = 0*0 + 1*2 + 2*3 + 0*0 = 4.

Используя вышеуказанную формулу умножения матриц, получим:

.

Из полученной матрицы R3 следует, что в исходном графе между вершинами, например, x 1 и x 2, существует 4 маршрута длиной 3: S1 = (x 1, x 2)(x 2, x 1)(x 1, x 2); S2 = (x 1, x 2)(x 2, x 4)(x 4, x 2); S3 = (x 1, x 3)(x 3, x 1)(x 1, x 2); S4 = (x 1, x 3)(x 3, x 4)(x 4, x 2).

Пример 2. Для графа, изображенного на рис. 15.29, привести примеры маршрута, цепи, цикла, простой цепи и простого цикла.

Рис. 15.29. Пример графа G

Ответ: Маршрутом в графе является любая конечная последовательность ребер, причем маршрут может проходить через одну и ту же вершину или ребро любое число раз. Тогда в качестве маршрута можно принять такую конечную последовательность: S = (x 1, x 2), (x 2, x 6), (x 6x 2), (x 2x 7), (x 7x 6), (x 6x 2). Цепью называют маршрут, не имеющий повторяющихся ребер. Таким образом, последовательность S = (x 1, x 2), (x 2, x 4), (x 4, x 6), (x 6, x 2), (x 2, x 7) можно считать цепью. Цикл представляет собой замкнутую цепь, т. е. цепь, у которой первая и последняя вершины совпадают. Тогда последовательность C = (x 1, x 5), (x 5, x 3), (x 3, x 1), (x 1, x 8), (x 8, x 5), (x 5, x 1) является циклом. При это, как мы видим, цепь и цикл могут проходить несколько раз через одну и ту же вершину. Простая цепь (цикл) не может включать в себя ни повторяющихся ребер, ни вершин. Примером простой цепи может служить последовательность S = (x 1, x 2), (x 2, x 4), (x 4, x 6), (x 6, x 8), (x 8, x 3); а простой цикл C = (x 1, x 5), (x 5, x 3), (x 3, x 1).

Пример 3. Для графа, заданного на рис. 15.30 привести пример разреза, правильного разреза.

Ответ: Правильными разрезами будут: U1 = {(x 3, x 6), (x 4, x 6), (x 4, x 7); U2 = {(x 4, x 10), (x 5, x 10)}; U3 = {(x 5, x 12)}; U4 = {(x 5, x 15)}. А разрез U определяется как их объединение: U = U1 È U2 È U3 È U4.

Рис. 15.30. Пример графа G

 

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Что из себя представляет маршрут в графе?

2. Как определяется длина маршрута?

3. Что такое маршрут в графе. Как определяется длина маршрута?

4. Дайте определение цепи, цикла, простого цикла и простой цепи в графе.

5. Какой граф называется связным?

6. Что такое компонента связности?

7. Что такое блок графа?

8. Дайте определение разреза, правильного разреза графа. Приведите примеры.

9. Дайте определение вершинной связности. Приведите примеры.

10. Дайте определение реберной связности. Приведите примеры.


Дата добавления: 2015-10-26; просмотров: 177 | Нарушение авторских прав


Читайте в этой же книге: Составить ГСА вычисления по формуле K! | Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 1 страница | Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 2 страница | Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 3 страница | Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 4 страница | Графический способ. | Теорема о функциональной полноте | КРИТЕРИИ ОЦЕНКИ | Способы задания графов | Примеры РЕШЕНИЯ ЗАДАЧ |
<== предыдущая страница | следующая страница ==>
Маршруты, цепи, циклы| Алгоритм Форда

mybiblioteka.su - 2015-2024 год. (0.009 сек.)