Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрации Техника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ? Влияние общества на человека Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления	Главная Избранные Случайная статья Познавательные Новые добавления Обратная связь FAQ Постройте для графа G ( V , E ), заданного геометрически, ⇐ ПредыдущаяСтр 9 из 10Следующая ⇒ а) матрицу смежности; б) матрицу инцидентности.   0) 1 2 3 4 5 6     1) 1 2 3 4 5 6   2) 3 4 5 2 1   1 6 3) 5 4 1 3 2 4) 2 5     3 4 5) 4 1 2 6 3 5   6) 4 3 2 1 6 5	7) 2 3 4 1 6 5
8) 2 3 6 1   5 4	9) 1 3 5 6 2 4

7)

2. Постройте для графа G (V, E), заданного геометрически

Матрицу смежности и матрицу инцидентности.

Задайте граф как алгебраическую систему.

Подсчитайте валентность вершин.

Определите тип графа.

9)

a

d

c

b

f

e

a

b

c

e

f

0)

3)

6)

1)

4)

7)

2)

5)

8)

a

b

c

e

d

f

a

b

d

f

c

b

c

f

d

a

b

c

d

f

3. Орг раф задан геометрически. Постройте матрицу смежности орграфа.

0) 1 2 3 6   4 5	2 1 1) 6 5 4 3
2) 1 3 4 5 2   1 7	3) 3 2 5 4 1
4) 2 3 4 5 6	5) 3 6 7 4 2 1 5

6)

2

3

4

1

6

5

 

 

1

7)

3

4

1

2

5

 

 

 

8)

2

3

5

6

 

 

4

9)

5

4

3

1

6

2

4. Дана матрица смежности орграфа. а) Задайте орграф геометрически, в) постройте матрицу инцидентности.

0) 1) 2) 3) 4)

5)   6) 7) 8) 9)

Практическое занятие №12. Задачи оптимизации на графах. Эйлеровы и гамильтоновы графы.

 

Элементы теории

 

Если дуге ориентированного графа G₁ (V, E) поставлено в соответствие некоторое вещественное число a (u, v), называемое весом, то последовательность вершин v ₀, v ₁,..., v_p определяет путь в G₁ а его длина определяется как сумма весов: .

Если в произвольном графе вес каждой дуги равен единице, то длина пути равна числу дуг.

Задача о кратчайшем пути возникает чаще всего при решении транспортных и дискретных задач динамического программирования и др.

Длину кратчайшего пути обозначают r (v_i, v_j) и называют расстоянием от v_i до v_j (расстояние может быть отрицательным). Для любого орграфа можно построить матрицу расстояний R=r (i, j).

Заполняется матрица построчно, выбирая вершину слева (справа). Значением является наименьшее число дуг, связывающее вершину слева с одной из вершин строки.

Если не существует ни одного пути из v_i в v_j, то полагаем r (v_i, v_j) = ¥. Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v₁,..., v_p не будет повторов.

Среднее отклонение вершины v_i от центра графа D(v_i) равно:

 где m - число дуг в графе, v - пробегает вершины графа, n – количество вершин графа, i = 1…n.

Вершина, для которой D(v_i) окажется минимальным, называется центром графа (возможно несколько вершин – центр графа).

Путем или маршрутом на графе G₁(V,E) называется последовательность его вершин и ребер v ₁ e ₁ v ₂ e ₂ v ₃ … v_ne_n v_{n +1}, в которой любые два соседних элемента инцидентны.

Путь называется простым, если все ребра и все вершины на нем, кроме первой и последней, различны.

 

Путь называется цепью, если все его ребра различные. Маршрут называется простой цепью, если все его вершины, а значит и ребра, различные.

 

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

  Цикл называется простым, если в нем нет одинаковых вершин, кроме первой и последней, т.е. если все вершины различны.

Связный граф без циклов называется деревом.

Примеры выполнения заданий

2

7) 1. Орграф задан геометрически. ⇐ Предыдущая12345678910Следующая ⇒ Поделиться: Читайте также:  Психологические особенности спортивного соревнования Приготовление дезинфицирующих растворов различной концентрации Занятость населения и рынок труда Социальный статус семьи и её типология 
		Последнее изменение этой страницы: 2021-05-27; просмотров: 106; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.135.198.49 (0.015 с.)