Теория графов и комбинаторика

Обознатам Ъ - ( t!(; , 1.-1) vi[~ миоявотао должвоотей; Р- | f j ^ j =1,^1] - множество претендентов; pj. ^ l--(7w - мно;?.ботс<о игяД таидентов, могущих работать на додиности d i . Рапснотгим дв^- дольний граф X ) , гда У - : р € 1. Очевидно, вопрос назначениях оводатоя к оу!Ц0от £ <паон:!К' пп .—ого паросочетания в поотроенпок даудольяом графе G- из ]) в Р и рошпо'^оя с помощью теорош Холла. Твотэама 8.6. Рашение задачи' о назначениях оущеотвуст 'гогдгч и только тогда, когда \/ !<-•(? и - общсо число претендентов на ЛК'ЧА R KOJDKIOQTET: ЦЕ меньше К . ГЛАВА 9, ЛЛРЕВЬЯ. ФУДЦАЮТАЛЫШЕ CKCTE ® ЦИКЛОВ И РАЗРЕЗОВ. ЦЕНГШ И ЦЕНТРОИда ГРАФОВ Связнооть графа является вашшм уоловием jjemenHfl многих задач. Наиболоа п р о о т ш ка овяз1шх графов являются деревьл. С деревьями овязанн такие важные понятия, как понятая ци1Ш1чэоко- го U кошяошчвокого рангов графов и систем циклов и разрезов. §9.1, Птазнаки деревьев , Граф без циюхэ называется ацикличьлшм ют деоом. Дерезой называется связный ациклический граф. Если ^ - лео, то нажд' л ого комаонента является деревом. Остовом овязйого г рфа к а - зыпаетоя ei-'o оотовной подграф, являющийся деревом, Связшй. под- Г(>;,1ф дерева Т иазЕ1-Г|0тоя поддеревом Т . Кодеревсм остма Т называется дояодаание f остова Т в графе $ , т.е. Т - оотов­ ной подграф Й- , содержащий те и только те ребра графа , кото­ рые Н9 входят в Т . . .Признаки деревьев дает следующая теорема. Теорема 9 . 1 . CPi ) ~ ^ ) является' деревом тог­ да и только ' тогда, когда в: юлнявтоя одно ив следующих условий: а) лкк5ы^| две вб|ШШ в Т соединены единственной простой ДЙДЫО; . • ) Б: - ОЭЯЭ!?!-"' ,1 I •в) - вди|з||;|еок^ и ^ = ^'•<••1. Приведем довдзаталъство этой тесреш, I . " ? - дерево''' •=ф, "а". Допустим, чтод т пекоторнх вер- . шин т/' , даа проотие { It- ЬТ ) ~ цепи Р, 9 Т о г ­ да , как -1дно''й1 8 графе 9 имеется проотой цикл, что npoTHgi^pf^^' (опаоание этого простого цикла предотав- ляетоя чи1!атвд1о).. ' ' • • J V 53