Максимальное и наибольшее
На множествах, графах и последовательностях[1] отношение включения задаёт частичный порядок, т. е. существуют как сравнимые пары множеств, графов и последовательностей (когда хотя бы одно множество из пары включается в другое, или же хотя бы один из графов является подграфом другого, или же одна последовательность является частью другой), так и несравнимые (в противном случае). Дальнейшее повествование пойдёт о графах, но с тем же успехом относится ко множествам, последовательностям и не только.
В связи с тем, что порядок на графах лишь частичный, в отличие например от отношения порядка для действительных чисел, при рассмотрении совокупности [math]\mathcal{G}[/math] графов можно выделить максимальные по включению графы в этой совокупности, т. е. те графы, которые не являются подграфами других графов из [math]\mathcal{G}[/math]. В то же время можно выделить в [math]\mathcal{G}[/math] самые большие графы по числу вершин (или рёбер)[2]. В разных аспектах могут представлять интерес как первые, так и вторые, при этом термины «максимальный по включению граф» и «самый большой по числу вершин граф» получаются достаточно громоздкими, если для исключения неоднозначности их использовать каждый раз полностью. Поэтому ещё на заре развития теории графов были приняты определённые договорённости: так, максимальные по включению графы называются просто максимальными (англ. maximal), а самые большие по числу вершин — наибольшими (англ. maximum), см. «Лекции по теории графов» и др. Легко видеть, что всякий наибольший граф в совокупности [math]\mathcal{G}[/math] является максимальным, но обратное, вообще говоря, неверно. Аналогичным образом определяются термины минимальный и наименьший.
Заметим, что у взвешенных графов существует другая численная характеристика — сумма весов рёбер, тогда появляется ещё граф наибольшего веса (или же граф максимального веса, поскольку для чисел понятия наибольшего и максимального совпадают).[3] При этом не всякий наибольший граф будет графом наибольшего веса, равно как и не всякий граф наибольшего веса будет наибольшим графом. Вообще говоря, граф наибольшего веса может даже не являться максимальным.
Определённую путаницу вносит перевод книги «Алгоритмы: построение и анализ» (Кормен Т. и др.) на русский язык, где вместо термина «наибольшее паросочетание» используется «максимальное паросочетание», тем не менее в оригинале авторы использовали общепринятую терминологию (maximum matching), поэтому рекомендуем простить авторам перевода это досадное недоразумение и не обращать на него внимания.
Стоит отметить, что с теоретической и практической точки зрения представляют интерес такие задачи, как поиск наименьшего максимального независимого множества (minimum maximal independent set), поиск наименьшей максимальной клики (minimum maximal clique), поиск наименьшего максимального паросочетания (minimum maximal matching), поиск наибольшего минимального разреза (maximum minimal cut) и др., поэтому есть необходимость различать понятия «максимальный» и «наибольший».
Замечания
- ↑ Напомним, что маршрут, цепь, цикл, путь и контур являются последовательностями, но могут рассматриваться как подграфы.
- ↑ Множества — по мощности, последовательности — по длине.
- ↑ Цепь и путь наименьшего веса также называют кратчайшими, а остов наименьшего веса — минимальным остовом (неоднозначности в данном случае не возникает, поскольку все остовы одного и того же графа содержат одинаковое число вершин и рёбер и попарно не содержатся друг в друге).
Литература
- А. А. Зыков Теория графов // Итоги науки. Алгебра. Топол.. — М.: ВИНИТИ, 1963. — С. 188–223.
- А. А. Зыков Основы теории графов. — М.: Наука, 1987. — 383 с.
- В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич Лекции по теории графов. — М.: Наука, 1990. — 384 с.
