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

На рпо.3.4 показате примеры оласЗо ( а ) , сильно ( ^ ) и односторонне ( ^ ) овязних орграфов. В орграфа d нет путей и нет [ f i - ' T i , )-путей, поэтому он не является ira одно­ сторонним, ни сильным. Ооновашо этого графа связно, лсзтоглу этот орграф олабнй. Орграф i слабый, но на сильный, т . к . в нем нот, HanpHMujj, ) - п у т ^ Он одноотороккйй, т . к . для любых двух вершин fc, можно соединить путом или первую 00 второй, пщ вторую с первой. В ооответотвии о этиш :зпр0д9лониягл1 вводатся ЛОЕЯТИЯ оильной, слабой и одаоомротаей кошоненты 1 >ри0нтарованного графа. Сильная компонента - максимальный сильно связный подграф, олабая компонента - максимальный слабо связный подграф, одноото- роннял компонента - максимальный односторонне связ1щй подграф. а ) б) в ) Рис.3.4 В случае симметричных орграфов все три понятия связности и BOG три разновидаюсти компонент совпадают о оостветствуищими поштиями для неориентированных графов. Из определений следует, ^-"с из сильной овязнооти следует однооторонняя связность и олабая связность; из односторонней овязнооти оледуат. слабая овяэностъ. Примеры рис.3.4 показывают, чти обратные утваркдения не оправвддивы. §3.4. Расстояния • . Расотойнием мезвду вершинами V и ft^-овяаного графа 06 Xj называется наименьшая из дтшн простых ( 1Г-Ы^ )-^апдй. Обозна­ чается раеотояйие символом ^ (i^) ) . • Учитывая результаты лемм 3 . 1 , 3 , 2 , расотоянив меаду ворш- .намн можно определить как наименьщую из длин (IT-'U?' )-маршру­ тов, • 25