8.8. Замечания, касающиеся литературы

Общей литературой, рекомендуемой для дальнейшего изучения связности и паросочетаний, являются [8.8, 8.26]. Берж [8.26] представляет также детальное обсуждение вопросов реализуемости последовательностей степеней и для случая ориентированных, и для случая неориентированных графов. Харари [8.8] излагает историю теоремы Менгера и дает несколько ее вариаций.

Графы служат моделью сетей связи. При изучении моделируемых графами сетей возникает понятие «уязвимость». Под уязвимостью мы понимаем чувствительность сети к воздействию. Сеть считается «разрушенной», если после удаления нескольких вершин или ребер получившийся в результате граф будет несвязным. Таким образом, уязвимость сети связана с вершинной и реберной связностями сети. Например, сеть может считаться более уязвимой, чем сеть , если вершинная связность у меньше, чем .

Боеш [8.27] опубликовал несколько статей по построению графов с заданными свойствами связности и надежности. Этой же теме посвящены работы Для дальнейшего изучения этой темы рекомендуется работа [8.21].

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

Для дальнейшего изучения паросочетаний и теории трансверса-лей очень рекомендуются работы Применение теории паросочетаний (в частности, к задаче оптимального назначения и задаче составления расписаний) и соответствующие алгоритмы обсуждаются в разд.