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

Ti Гзь 1Гз 1Гг *= Рио.2.7 Пусть 6 ' ~ C V , r ) _ симметричный о^т-раф\ - симметричные д у г и , ооединязощие вершины V vi ЬУ , Двухэлементное множество Hi-jHBasTCH I 'dpoM и обозначаатоя Этг соглашение позволяет установить связь мегкг' понятижли симмет­ ричного орграфа и нроотого графа. Любой симметричный орграф можно пог 'чоть Kaic простой граф, каадое ребро которого ооответ'-"вует паре симметричных дур о т е ш же концаш и каждый простой граф можно понимать как сответотвующий симметричный орграф. Отсвда следует, что теория простых графов является теорией сймглетрпч- ных орграфов. Таким образом, понятие орграфа .( ГЙ ,:' ЯП '.'.^ Я более об­ щим по оравненаю о понятием лроотого rpafiia. В дальнейшем поня­ тия графа и симметричного орграфа отождествляется. ^ Основанием орграфа & - ( \ / , Г ) называь ая граф &-CVjX), по<1уч0кный оамматрцзацией (? . Напримрт, граф на рис.2.7 явля­ ется оокованиам орграфа .la рио.2.6, а и может быть изображен в виде I'l, • «"i ^ Рйо.2,8 /V Множество ребер У основания S- орграфе <? мозк:^ задать в виде: X = f^ir, и г } : С г»-, КГ) б V( Ц гг) е Г } . Пуоть & - пхюийвольный орграф, '{Гб V . Полуоте- оенью исхода ввришнк V называется число ( V ) иоходшцих иа 8ТСЙ вврши1ш д у г ; с( "(tr) S./ { Y& Г'• 1^" =f7/>i Т } I. Полуохепеный захода вершины 'У называется число й'?!'') дуг, ваходшцих в iT .* K V e Г : } I . Степень dCif) В01и1ины iT орграфа равна сумме ® W t e/^fjr), Аналогом теоремы 2 . 1 для орграфов является слелующая Теорема З .Э. В любом орграфе G~ (V,Г ) оумма пслуотепеней исхода всех вершин равна сумме их оолуствпеней захода; ^ Л =X. , и- f i r ) . , „ , V 1Г6^ «r«V Vib."/ 16