1. Используя алгоритм генерации варианта GV (приложение А), построить неориентированный граф G: GV(7,{2,3}).
2. Описать граф матрицей смежности и матрицей инцидентности.
3. Изобразить графически граф G и его дополнение .
4. Построить произвольный остовный подграф и подграф, порожденный вершинами {1,2,5,6,7};
5. Построить все помеченные 5-графы, изоморфно вложимые в граф G. Определить классы изоморфных графов, построив биекцию их вершин. Для каждого класса изоморфных графов привести рисунок абстрактного графа.
6. Построить все помеченные (5-7)-графы (до 20 штук), изоморфные некоторому подграфу G. Определить классы изоморфных графов, построив биекцию их вершин. Для каждого класса изоморфных графов привести рисунок абстрактного графа.
7. Найти все максимальные и наибольшие независимые множества исходного графа, определить число независимости.
8. Найти все максимальные и наибольшие клики данного графа. Определить плотность графа G.
9. Найти все минимальные и наименьшие доминирующие множества, определить число доминирования.
10. Найти полный двудольный подграф Kp,q, изоморфно вложимый в G с максимальным количеством вершин p+q (p≠1). Найти звезду , изоморфно вложимую в G с максимальным q.

1 ответы

  • 1. Используя алгоритм генерации варианта GV (приложение А), построить неориентированный граф G: GV(7,{2,3}).

    2. Описать граф матрицей смежности и матрицей инцидентности.

    3.Изобразить графически граф G и его дополнение  .

    4. Построить произвольный остовный подграф и подграф, порожденный вершинами {1,2,5,6,7};

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

    Для каждого класса изоморфных графов привести рисунок абстрактного графа.

    6. Построить все помеченные (5-7)-графы (до 20 штук), изоморфные некоторому подграфу G. Определить классы изоморфных графов, построив биекцию их вершин. Для каждого класса изоморфных графов привести рисунок абстрактного графа.

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

    8. Найти все максимальные и наибольшие клики данного графа. Определить плотность графа G.

    9. Найти все минимальные и наименьшие доминирующие множества, определить число доминирования.

    10. Найти полный двудольный подграфKp,q, изоморфно вложимый в Gс максимальным количеством вершин p+q (p≠1). Найти звезду  , изоморфно вложимую в Gс максимальным q.

Последний по теме Математика

Угол между наклонной и плоскостью равен 30 градусам, длина наклонной равна 6 см. Найдите длину проек

Преобразовать и построить кривую x²-6x+2y+7=0

Срочно! Смешали 10% и 20% растворы соли и получили 12 литров 20% Сколько литров 25% раствора было

Помогите, пожалуйста Область значений и график функции...

Кут при вершині рівнобедреного трикутника дорівнює 30° , на бічну сторону опущена висота . Знайти ку

4. Теплоход был в пути 19 чв течение двух дней. В первый день он прошёл 200 км, а во второй 180 км

Найти корни уравнения cos x = - 1/2 на промежутке 0; 2п

Вы можете решить эти два вопроса, пожалуйста?

Найти наименьшее целое значение a, при котором уравнение x^2-(a+11)x-3a-17=0 имеет два различных кор

Sin(2*x)= 1/2 решите пожалуйста уравнение