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

V i . Ts"' П0ТЛИ; T-t " кратюде дуги; Ts » 3^ - кратные П0ТЛЙ. О ' Г з V p . т . X Рио.2.5 Еоли нериапш орграфа паренумарованн, то удобно оббзначать через Tij" дугу ( f i , V- ) , ооеданящую вершину b^L о вершиной Дуги Т ,оС. графа G - ( V j Г ) назнваютоя оимметри'чными, ооли vTe.Y Tairae, что Т ~ 'к . В гра­ фа. изобраиенном на рис.2.5 ITJ и - пара с .жетричных дуг. Орграф (? = (V j Г ) называется опжетричным орграфом, еоли ё\1сT i i & r ^ r j c ^ r ) . орграф называется направленным или антиоимметричным, волн ок не содержит оотшетричннх пар дуг. На рис,2.6 показаны диаг­ раммы ..аоимметричного, оимметричного и направленного орграфов. „т . <4 • % . а.) л ' " ' Рио.2.6 СишетризациеЙ орграфа называетоя операция, при Kjj?opoS орграфу 9- отавится^в соотнетотвке стметричный орграф , ^ =C V > r ) ^ , в котошм Р " Г и {(V,iO')(чг^иг) ё Г \ / (vr,-!;-)er Орграф ? , получинный опиоаннш образом, называетоя сим- метризовашшм орграфом (? . Из определения следует, чТо при оим- , метризации орграфа & добанляютоя оимметричные дуги для всох дуг графа & , которые .оимметричных ду г в (? не имели. Напри­ мер, при оимметривации графа на рис.2.6,а, получается симметрич­ ный орграф, изображенный на ри^.2.7. Симметризованный орграф & яаляетоя наименьшим оишотрич- ным надграфом орграфа (9 . 1 5