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

Ввадепноа понятие paooTOHifflfl удовлетворяет аксиомам метрики: I ) неотрицательность 2 ) оищлетричиоотъ Vir, »!?" \^ С1Г^гСг)~ ; 3 ) правило тре­ угольника it.). Справвдаивоотъ первой аксиомы нопоорвдотввнно получается из определения раостояния, вторая аксиома следует из неориен- тированнооти графа. Еоли оущаотвувт ( - J T - ) - м а ршр у т длины ^ , то сущйотвубт ('U^-lT ).^""ргарут той же дашнн j . Справедли­ вость правила треугольника вытекает из следующих раооуждений. Еоли Ир, соотввтотвенно кратчайшие ростае ) т о 0Ц9П- Kt лтйх простых цепей y*i s - u T P j _ является (.V'-h, )-мар- шрутом дзшны l y c / i j j z : f (V^uT) . По опрвдвлению расстоя­ ний , ^то и требовалось доказать. Если в орграфе ( V j P ) для вервган IT к ЬУ существует ( )-11уть, то говорят, что вершина иУ достижима из вер- Шклы тГ . Отношение доотижимооти верш'" транзитивно. Если орграф окммагричный, то это о'-.лошвние яиляетоя симметричным, т . е . дос- тикимооть взаимна^ Считеетоя, что каждая вершина достижима из себя о помощью пути нулевой длины. Поэтому отношение достижи­ мости рв^ихекоивно. При решении прикладных вадач, моделируемых графами, возникают оледующие вопросы: 1 , Каково наимекыпеб число вврш;ш графа, иа которых дости­ жима лмйая другая вершина графа? 2 . Каково наибольшее 4"'wio вершин, которые взаимно длотига- мн? Обозначим множество вершин достижимых из звршины1Г , называемое областью достижимости вершины V или доотижимым множеством, Еоли ограничитьс; раоомотрвиием путей длины I , то R<ir)i=. Pcv). , г де Гспг) - множество образов вершины тУ , Мно- «ветво Г(Г сV ) ) =r^CV) оостоит из вершин, достижимых из 1Г о помощью путей длины 2 . Множество Г с г ) - множество верши", доотаяшмнх И8 о помощью путей длины К . Каж ая вершина kCtr} доотижима из tT о помощью путей доп!нн ' К при не­ котором конечном значении К . Следовательно, Й6