ГЛАВА III. СВОЙСТВА ГРАФОВ

§ 24. Введение

В конце предыдущего параграфа с помощью поняшя сот изучались комбинаторные задачи о размещениях по ячейкам, причем в часть из них помещать элементы было запрещено. Тем самым ячейки сот разбивались на два подмножества: ячейки, обладающие некоторым свойством и ячейки, не обладающие им (т. е. обладающие свойством Всякий раз, когда это имеет место, говорят, что множество реализует граф. На рис. 70 приведен пример графа.

Рис. 70.

Рис. 71.

Этот термин широко обсуждался, и некоторые считают, что этимологически предпочтительнее заменить его термином «грамма» (используя аналогию: телеграф — инструмент, а телеграмма — сообщение, передаваемое этим инструментом), но мы будем придерживаться обычной терминологии.

Под графом, следуя Кёнигу [21] и Бержу [8], мы будем понимать разбиение теоретико-множественного произведения некоторого счетного множества на себя на две части. Графы рассматриваются во многих областях математики, и мы посвящаем им значительную часть книги.

Рассмотрим рис. 70, изображающий граф. На нем можно разглядеть пуделя, но рассмотрения такого рода нас не интересуют (в противоположность комбинаторной топологии). Этого пуделя можно представить подмножеством пар

или так, как это сделано на рис. 71, где пара изображена стрелкой. Все эти способы изображения графа эквивалентны, и в каждом конкретном случае мы будем пользоваться тем из них, который более удобен.

Рис. 72

Рис. 73.

Например, на рис. 72 при некотором воображении можно представить себе перекресток двух улиц с односторонним движением, чего нельзя сказать о том же графе, изображенном на рис. 73; только математику легко усмотреть их изоморфизм.

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