Задача: Запрещенный подграф
Два неориентированных графа G и H называются изоморфными , если:
- они имеют одинаковое количество вершин;
- существует такое однозначное соответствие между их вершинами, что любые две различные вершины графа G соединены ребром тогда и только тогда, когда соединены ребром соответствующие вершины графа H.
Например, следующие два графа изоморфны, хотя выглядят по-разному:
Возможным однозначным соответствием, показывающим, что эти два графа изоморфны, является {a-1, b-6, c-8, d-3, g-5, h-2, i-4, j-7}, хотя существуют и другие подобные соответствия.
Подграфом графа G называется граф, множества вершин и ребер которого являются подмножествами множеств вершин и ребер графа G. Заметьте, что граф G является также и своим подграфом. На рисунке показаны граф и один из его подграфов:
Говорят, что граф G содержит другой граф H , если существует хотя бы один подграф H ’ графа G , который изоморфен H . Следующий рисунок показывает граф G , который содержит граф H .
ЗАДАНИЕ
По двум заданным неориентированным графам G и H постройте подграф G’ графа G такой, что:
количество вершин в графах G и G’ одинаково;
H не содержится в G’ .
Естественно, может быть много подграфов графа G’ с перечисленными свойствами. Постройте подграф с как можно большим количеством ребер.
БАЗОВЫЙ АЛГОРИТМ
Возможно, наиболее простой стратегией при решении этой задачи будет следующая: рассматривать ребра графа G в порядке, в котором они представлены во входных данных, после чего пытаться добавлять ребра одно за другим в граф G’, проверяя на каждом шаге, входит ли граф H в граф G’ или нет. Правильная реализация этого жадного алгоритма наберет некоторое количество очков, хотя существуют гораздо лучшие стратегии.
ОГРАНИЧЕНИЯ
3 ≤ m ≤ 4 m – количество вершин в H.
3 ≤ n ≤ 1000 n – количество вершин в G .
ВВОД
Вы получите 10 тестов каждый со следующими данными:
|
Пример ввода
|
ОПИСАНИЕ
|
|
3 5
0 1 0
1 0 1
0 1 0
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
0 0 0 1 0
|
СТРОКА 1: Содержит два целых числа, разделенных пробелом, соответственно m и n.
СЛЕДУЮЩИЕ m СТРОК: Каждая строка содержит m целых чисел, разделенных пробелами, и представляет одну вершину из H в порядке 1, ..., m . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в H , и равняется 0 в противном случае.
СЛЕДУЮЩИЕ n СТРОК : Каждая строка содержит n целых чисел, разделенных пробелами, и представляет одну вершину из G в порядке 1, ..., n . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в G , и равняется 0 в противном случае.
|
Заметьте, что за исключением строки 1, приведенные входные данные представляют собой матрицы смежности графов H и G .
ВЫВОД
Вы должны создать 10 выводов по одному на каждый входной. Каждый тест должен содержать следующие данные:
|
Пример вывода
|
ОПИСАНИЕ
|
|
#FILE forbidden K
5
0 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
|
СТРОКА 1: Заголовок файла. Заголовок файла должен содержать
#FILE forbidden K
где K – это число между 1 и 10, которое соответствует решенному входному файлу.
СТРОКА 2: Содержит одно целое число : n .
СЛЕДУЮЩИЕ n СТРОК : Каждая строка содержит n целых чисел, разделенных пробелом, и представляет одну вершину из G’ в порядке 1, ..., n . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в G’ , и равняется 0 в противном случае.
|
Заметьте, что за исключением строк 1 и 2, приведенные входные данные представляют собой матрицу смежности графа G’. Обратите внимание, что есть много вариантов ответа, и приведенный вариант является корректным, но не оптимальным.
Ваш ответ: