1. Главная
  2. Библиотека
  3. Высшая математика
  4. Ориентированный граф задан матрицей инцидентности Ответ...
Решение задачи на тему

Ориентированный граф задан матрицей инцидентности Ответьте на поставленные вопросы (1) Чему равна полустепень исхода вершины 4? (2) Сколько изолированных вершин у графа? (3) Сколько дуг входит в цикл наибольшей длины на графе? (4) Сколько дуг входит в

  • Высшая математика
  • #Математический анализ
  • #Дискретная математика
Ориентированный граф задан матрицей инцидентности Ответьте на поставленные вопросы (1) Чему равна полустепень исхода вершины 4? (2) Сколько изолированных вершин у графа? (3) Сколько дуг входит в цикл наибольшей длины на графе? (4) Сколько дуг входит в

Условие:

Ориентированный граф задан матрицей инцидентности

1010-1000
0-1-110000
000-1011-1
-11001-1-11
00000000


Ответьте на поставленные вопросы
(1) Чему равна полустепень исхода вершины 4?
(2) Сколько изолированных вершин у графа?
(3) Сколько дуг входит в цикл наибольшей длины на графе?
(4) Сколько дуг входит в цепь наибольшей длины на графе?

Ответ дайте в формате последовательности чисел без пробелов, скобок и запятых (например, 9135): на первое место поставьте ответ на вопрос (1), на второе - ответ на вопрос (2); и т.д.

Решение:

Рассмотрим матрицу инцидентности, где строки соответствуют вершинам (1, 2, 3, 4, 5), а столбцы – дугам (обозначим их 1,2,…,8). При стандартном определении для ориентированного графа: – если в столбце стоит 1, то вершина является истоком дуги; – если стоит –1, то вершина является приемником дуги.

Проанализируем каждый столбец (дугу):

  1. Столбец 1: строка 1 = 1, строка 4 = –1 → дуга из 1 в 4.
  2. Столбец 2: строка 4 = 1, строка 2 = –1 → дуга из 4 в 2.
  3. Столбец 3: строка 1 = 1, строка 2 = –1 → дуга из 1 в 2.
  4. Столбец 4: строка 2 = 1, строка 3 = –1 → дуга из 2 в 3.
  5. Столбец 5: строка 4 = 1,...

Выбери предмет