1. Главная
  2. Библиотека
  3. Геометрия
  4. Произведите следующие операции над графом G ) удаление...
Разбор задачи

Произведите следующие операции над графом G ) удаление вершины 1 графа G б) запишите изолированные и висячие вершины в полученном графе в) стягивание ребра [5,2] графа G г) перечислите ребра полученного графа Постройте граф . Определить вид графа

  • Предмет: Геометрия
  • Автор: Кэмп
  • #Дискретная математика
  • #Теория графов
Произведите следующие операции над графом G ) удаление вершины 1 графа G б) запишите изолированные и висячие вершины в полученном графе в) стягивание ребра [5,2] графа G г) перечислите ребра полученного графа Постройте граф . Определить вид графа

Условие:

A(G)=[110001101000001110000011010010000000]A(T)=[110001111000001110001100001111000001] \mathrm{A}(G)=\left[ \begin{array}{llllll} 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right] \quad \mathrm{A}(T)=\left[ \begin{array}{llllll} 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right]
  1. Произведите следующие операции над графом G\na) удаление вершины 1 графа G б) запишите изолированные и висячие вершины в полученном графе в) стягивание ребра [5,2] графа G г) перечислите ребра полученного графа
  2. Постройте граф H=G⊕T\mathrm{H}=\mathrm{G} \oplus \mathrm{T}.

Определить вид графа

Решение:

1. Операции над графом GG

a) Удаление вершины 1 графа GG

Матрица смежности графа GG выглядит следующим образом:

A(G)=[110001101000001110000011010010000000] \mathrm{A}(G)=\left[ \begin{array}{llllll} 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right]

Удаляем вершину 1 (первую строку и первый столбец):

A(G′)=[0100101110000110001000000] \mathrm{A}(G')=\left[ \begin{array}{lllll} 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right]

б) Изолированн...

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

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое действие соответствует операции удаления вершины из графа, представленного матрицей смежности?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Похожие задачи

Похожие задачи

Не нашел нужную задачу?Воспользуйся поиском

AI помощники

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

E
S
А
Б
В
Г
Д
Е
Ж
З
И
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Э
Я