Подпишитесь на наши новости
Вернуться к началу с статьи up
 

ГРА́ФОВ ТЕО́РИЯ

  • рубрика

    Рубрика: Математика

  • родственные статьи
  • image description

    В книжной версии

    Том 7. Москва, 2007, стр. 644-645

  • image description

    Скопировать библиографическую ссылку:




Авторы: В. Е. Тараканов
Рис. 1.
Рис. 2.

ГРА́ФОВ ТЕО́РИЯ, раз­дел дис­крет­ной ма­те­ма­ти­ки, в ко­то­ром изу­ча­ют­ся свой­ст­ва гра­фов и их обоб­ще­ний. Гра­фом на­зы­ва­ет­ся па­ра ($V, E$), где $V$ – мно­же­ст­во то­чек, на­зы­вае­мых вер­ши­на­ми, и $E$ – мно­же­ст­во пар вер­шин, при­чём ес­ли по­ря­док, в ко­то­ром пе­ре­чис­ле­ны вер­ши­ны в па­ре, не ва­жен, то эта па­ра вер­шин гра­фа на­зы­ва­ет­ся реб­ром, а ес­ли ва­жен – ду­гой. Граф, со­дер­жа­щий толь­ко рёб­ра, на­зы­ва­ет­ся не­ори­ен­ти­ро­ван­ным гра­фом, или про­сто гра­фом, а граф, со­дер­жа­щий толь­ко ду­ги, – ори­ен­ти­ро­ван­ным гра­фом. На рис. 1 – не­ори­ен­ти­ро­ван­ный граф с вер­ши­на­ми $a, b, c, d$ и рёб­ра­ми $(a, b), (b, c), (c, d), (a, d), (a, c), (b, d)$, на рис. 2 – ори­ен­ти­ро­ван­ный граф с вер­ши­на­ми $a, b, c, d, e, f$ и ду­га­ми $(a, b), (b, c), (c, d), (d, e), (e, f), (f, a)$.

Исторический очерк

Рис. 3.

Пер­вые за­да­чи Г. т. бы­ли свя­за­ны с ре­ше­ни­ем ма­те­ма­тич. за­дач раз­вле­ка­тель­но­го ха­рак­те­ра и го­ло­во­ло­мок (см. Ком­би­на­тор­ные за­да­чи клас­си­че­ские). Од­ним из пер­вых ре­зуль­та­тов Г. т. был кри­те­рий су­ще­ст­во­ва­ния об­хо­да всех рё­бер гра­фа без по­вто­ре­ний, по­лу­чен­ный Л. Эй­ле­ром (1736) при ре­ше­нии за­да­чи о Кё­нигс­берг­ских мос­тах (см. Га­миль­то­нов цикл). С сер. 19 в. по­яв­ля­ют­ся от­но­ся­щие­ся к Г. т. ра­бо­ты, со­дер­жа­щие ре­зуль­та­ты, свя­зан­ные с разл. при­ло­же­ния­ми ма­те­ма­ти­ки. Так, Г. Кирх­гоф (1847) для со­став­ле­ния пол­ной сис­те­мы урав­не­ний для то­ков и на­пря­же­ний в элек­трич. се­тях (см. Кирх­го­фа пра­ви­ла) пред­ло­жил пред­став­лять та­кую сеть гра­фом и на­хо­дить в этом гра­фе ос­тов­ные де­ре­вья, что при­во­дит к ре­ше­нию за­да­чи вы­де­ле­ния не­за­ви­си­мых сис­тем урав­не­ний. Де­ре­вом на­зы­ва­ет­ся связ­ный граф, не со­дер­жа­щий цик­лов (рис. 3), ос­тов­ное де­ре­во гра­фа – это его под­граф, пред­став­ляю­щий со­бой де­ре­во, мно­же­ст­во вер­шин ко­то­ро­го сов­па­да­ет с мно­же­ст­вом вер­шин гра­фа. А. Кэ­ли (1854) для под­счё­та чис­ла изо­ме­ров пре­дель­ных уг­ле­во­до­ро­дов при­шёл к за­да­чам опи­са­ния и пе­ре­чис­ле­ния де­ревь­ев, об­ла­даю­щих за­дан­ны­ми свой­ст­ва­ми. Тер­мин «граф» ут­вер­дил­ся в ма­те­ма­ти­ке по­сле вы­хо­да мо­но­гра­фии нем. ма­те­ма­ти­ка Д. Кё­ни­га (1936). На­чи­ная со 2-й пол. 20 в. зна­чи­тель­но рас­ши­ри­лись ис­сле­до­ва­ния в Г. т., в осн. в си­лу раз­ви­тия дис­крет­ной ма­те­ма­ти­ки и вы­чис­лит. тех­ни­ки. За­да­ние гра­фа рав­но­силь­но за­да­нию на эле­мен­тах мно­же­ст­ва вер­шин $V$ не­ко­то­ро­го би­нар­но­го от­но­ше­ния. По этой при­чи­не, а так­же вви­ду воз­мож­но­сти на­гляд­но­го пред­став­ле­ния гра­фа в ви­де чер­те­жа на плос­ко­сти, гра­фо­вые мо­де­ли ис­поль­зу­ют­ся при по­строе­нии ал­го­рит­мов ре­ше­ния раз­но­об­раз­ных за­дач как в ма­те­ма­ти­ке и ес­те­ст­во­зна­нии, так и в гу­ма­ни­тар­ных нау­ках.

Методы исследования в теории графов

Пре­ж­де все­го вы­де­ля­ют­ся ком­би­на­тор­ные ме­то­ды тео­ре­ти­ко-мно­же­ст­вен­но­го ана­ли­за за­дан­но­го би­нар­но­го от­ноше­ния на мно­же­ст­ве вер­шин. Весь­ма су­ще­ст­вен­ны (осо­бен­но в пе­ре­чис­ли­тель­ных за­да­чах) ал­геб­ра­ические ме­то­ды, в пер­вую оче­редь ме­то­ды тео­рии групп (в ча­ст­но­сти, групп под­ста­но­вок). При изу­че­нии ук­ла­док гра­фа на плос­кость при­вле­ка­ют­ся ре­зуль­та­ты то­по­ло­гич. ха­рак­те­ра. Слу­чай­ные гра­фы изу­ча­ют­ся с по­мо­щью тео­ре­ти­ко-ве­ро­ят­но­ст­ных ме­то­дов.

Осо­бую роль при изу­че­нии гра­фов иг­ра­ют мат­рич­ные ме­то­ды. Для гра­фа $G$ мат­ри­цей смеж­но­сти $A=A(G)=||a_{ij}||$ назы­ва­ет­ся мат­ри­ца, в ко­то­рой $a_{ij}=1$, ес­ли в гра­фе $G$ вер­ши­на $i$ свя­за­на с вер­ши­ной $j$ реб­ром (или ду­гой в ори­ен­ти­ро­ван­ном гра­фе) и $a_{ij}=0$ в про­тив­ном слу­чае. В пер­вом слу­чае го­во­рят, что вер­ши­ны $i$ и $j$ смеж­ны, во вто­ром слу­чае – что они не­смеж­ны. Мар­шру­том в гра­фе $G$ на­зы­ва­ет­ся по­сле­до­ва­тель­ность $v_0e_1v_1…v_{n–1}e_nv_n$, со­стоя­щая по­пе­ре­менно из вер­шин и рё­бер гра­фа, в ко­то­рой реб­ро $e_i$ со­еди­ня­ет вер­ши­ны $v_{i–1}$ и $v_i, i=1, …, n$; го­во­рят, что этот мар­шрут свя­зы­ва­ет вер­ши­ны $v_0$ и $v_n$. Мар­шрут, в ко­то­ром $v_0=v_n$, на­зы­ва­ет­ся цик­лом. Мар­шрут на­зы­ва­ет­ся це­пью (со­от­вет­ст­вен­но, про­стой це­пью), ес­ли все его рёб­ра (все его вер­ши­ны) раз­лич­ны. При $n⩾1$ эле­мент на мес­те $(i, j)$ в мат­ри­це $A^n$ ра­вен чис­лу мар­шру­тов дли­ны $n$ из вер­ши­ны $v_i$ в вер­ши­ну $v_j$. Граф на­зы­ва­ет­ся связ­ным, ес­ли для лю­бых его двух вер­шин су­ще­ству­ет мар­шрут, свя­зы­ваю­щий эти вер­ши­ны. Для гра­фа $G$ с $p$ вер­ши­на­ми и $q$ рёб­ра­ми, в ко­то­ром за­ну­ме­ро­ва­ны как вер­ши­ны, так и рёб­ра, рас­смат­ри­ва­ет­ся мат­ри­ца ин­ци­дент­но­сти $B(G)$, пред­став­ляю­щая со­бой мат­ри­цу, со­стоя­щую из ну­лей и еди­ниц с дву­мя еди­ни­ца­ми в ка­ж­дом столб­це; в столб­це, со­от­вет­ст­вую­щем реб­ру, со­еди­няю­ще­му вер­ши­ны $i$ и $j$, еди­ни­ца сто­ит в стро­ках с но­ме­ра­ми $i$ и $j$. Го­во­рят, что ка­ж­дая из вер­шин $i$ и $j$ и со­еди­няю­щее их реб­ро ин­ци­дент­ны, два реб­ра смеж­ны, ес­ли они име­ют об­щую ин­ци­дент­ную им вер­ши­ну. Ранг мат­ри­цы ин­ци­дент­но­сти $B(G)$ ра­вен $p-1$, ес­ли граф $G$ яв­ля­ет­ся связ­ным гра­фом.

Мно­же­ст­во собств. зна­че­ний мат­ри­цы смеж­но­сти гра­фа или ори­ен­ти­ро­ван­но­го гра­фа (при этом ка­ж­дое зна­че­ние бе­рёт­ся столь­ко раз, ка­ко­ва его крат­ность) на­зы­ва­ет­ся спек­тром гра­фа. Спектр гра­фа с $n$ вер­ши­на­ми со­сто­ит из $n$ дей­ст­ви­тель­ных чи­сел. Изу­че­ние спек­тра гра­фа по­зво­ля­ет вы­яс­нить мн. осо­бен­но­сти его строе­ния.

Задачи теории графов

Цен­траль­ным в Г. т. яв­ля­ет­ся раз­дел, изу­чаю­щий струк­тур­ные свой­ст­ва гра­фов. Од­ной из ха­рак­те­ри­стик струк­ту­ры гра­фа яв­ля­ет­ся по­сле­до­ва­тель­ность сте­пе­ней его вер­шин. Сте­пе­нью вер­ши­ны не­ори­ен­ти­ро­ван­но­го гра­фа на­зы­ва­ет­ся чис­ло ин­ци­дент­ных ей рё­бер. Гра­фич. раз­бие­ни­ем чёт­но­го на­ту­раль­но­го чис­ла $n$ на­зы­ва­ет­ся пред­став­ле­ние его в ви­де сум­мы $p$ сла­гае­мых $n=\sum_{i=1}^d d_i$ та­кое, что су­ще­ству­ет граф с $p$ вер­ши­на­ми, сте­пе­ни ко­то­рых рав­ны $d_1,…,d_p$. В Г. т. из­вес­тен эф­фек­тив­ный ал­го­ритм, по­зво­ляю­щий для дан­но­го упо­ря­до­чен­но­го на­бо­ра чи­сел $(d_1,…,d_p)$ оп­ре­де­лить, су­ще­ст­ву­ет ли граф с $p$ вер­ши­на­ми $v_1,…,v_p$, для ко­то­рых по­сле­до­ва­тель­ность сте­пе­ней $(d(v_1),…,d(v_p))$ сов­па­да­ет с этим на­бо­ром. Под­роб­но изу­че­но др. важ­ное струк­тур­ное свой­ст­во – связ­ность гра­фа, а так­же во­про­сы, от­но­ся­щие­ся к су­ще­ст­во­ва­нию в связ­ном гра­фе мар­шру­тов оп­ре­де­лён­но­го ви­да.

Спец. раз­де­лом струк­тур­ной Г. т. яв­ля­ет­ся фак­то­ри­за­ция гра­фа, т. е. раз­ло­же­ние гра­фа $G= (V, E)$ на сум­му фак­то­ров (под­гра­фов) $G_1, …, G_m$ с не­ко­то­рым за­дан­ным свой­ст­вом, где $G_i=(V, E_i)$ и $E=E_1\cup …\cup E_m$ – раз­бие­ние мно­же­ст­ва рё­бер на не­пус­тые не­пе­ре­се­каю­щие­ся под­мно­же­ст­ва. Наи­бо­лее рас­про­стра­нён­ные ви­ды фак­то­ри­за­ции: n-фак­то­ри­за­ция, где $G_i$ – од­но­род­ные гра­фы сте­пе­ни $n$ (гра­фы, сте­пе­ни всех вер­шин ко­то­рых оди­на­ко­вы и рав­ны $n$), и дре­вес­ная фак­то­ри­за­ция, где ка­ж­дая ком­по­нен­та лю­бо­го $G_i, i=1,…,m,$ яв­ля­ет­ся де­ре­вом. Лю­бой пол­ный граф $K_{2n}$, т. е. граф, в ко­то­ром лю­бые две вер­ши­ны смеж­ны, 1-фак­то­ри­зу­ем, но не 2-фак­то­ри­зу­ем; лю­бой пол­ный граф $K_{2n+1}$ не яв­ля­ет­ся 1-фак­то­ри­зуе­мым, но пред­став­ля­ет­ся в ви­де сум­мы $n$ фак­то­ров, яв­ляю­щих­ся цик­ла­ми. Ес­ли при 1-фак­то­ри­за­ции речь идёт о воз­мож­но­сти раз­бие­ния мно­же­ст­ва рё­бер на под­мно­же­ст­ва, со­стоя­щие из по­пар­но не­смеж­ных рё­бер (при этом ка­ж­дое из под­мно­жеств есть 1-фак­тор), то вся­кое раз­бие­ние мно­же­ст­ва вер­шин гра­фа на $n$ под­мно­жеств та­ких, что вер­ши­ны из лю­бых двух раз­ных под­мно­жеств по­пар­но не­смеж­ны, оп­ре­де­ля­ет пра­виль­ную рас­крас­ку гра­фа в $n$ цве­тов. Тео­рия рас­кра­сок гра­фа воз­ник­ла и раз­ви­ва­лась в свя­зи с че­ты­рёх кра­сок за­да­чей, ко­то­рая по­лу­чи­ла ре­ше­ние лишь на ру­бе­же 1970–80-х гг.

С гра­фом $G=(V, E)$ ес­те­ст­вен­но свя­зы­ва­ет­ся це­лый ряд гра­фов, напр. его под­гра­фы, до­пол­ни­тель­ный граф, рё­бер­ный граф $L(G)$. Рё­бер­ным для гра­фа $G$ с $p$ вер­ши­на­ми и $q$ рёб­ра­ми на­зы­ва­ет­ся граф с мно­же­ст­вом вер­шин $E$, в ко­то­ром две вер­ши­ны со­еди­не­ны реб­ром то­гда и толь­ко то­гда, ко­гда со­от­вет­ст­вую­щие рёб­ра смеж­ны в $G$. Кри­те­рий то­го, что дан­ный граф яв­ля­ет­ся рё­бер­ным гра­фом, за­клю­ча­ет­ся в от­сут­ст­вии у не­го под­гра­фов, при­над­ле­жа­щих мно­же­ст­ву из 9 кон­крет­но ука­зан­ных гра­фов (с 4, 5 или 6 вер­ши­на­ми). Изу­че­ние спец. клас­сов гра­фов, вы­де­ляе­мых к.-л. оп­ре­де­ляю­щим при­зна­ком или струк­тур­ным свой­ст­вом, со­став­ля­ет од­но из на­прав­ле­ний тео­рии гра­фов.

Ес­ли граф за­дан би­нар­ным от­но­ше­ни­ем на мно­же­ст­ве, то час­то воз­ни­ка­ет во­прос о том или ином его кон­крет­ном пред­став­ле­нии. Та­ко­го ро­да за­да­чей яв­ля­ет­ся за­да­ча о пла­нар­но­сти гра­фа, т. е. о воз­мож­но­сти пред­ста­вить его на плос­ко­сти ри­сун­ком, в ко­то­ром нет пе­ре­се­че­ния рё­бер. Наи­бо­лее из­вест­ный критерий пла­нар­но­сти да­ёт тео­ре­ма Пон­тря­ги­на – Ку­ра­тов­ско­го: граф яв­ля­ет­ся пла­нар­ным то­гда и толь­ко то­гда, ко­гда он не со­дер­жит в ка­че­ст­ве под­гра­фа ни пол­но­го гра­фа $K_5$, ни дву­доль­но­го гра­фа $K_{3,3}$. Граф $G=(V, E)$ на­зы­ва­ет­ся дву­доль­ным, ес­ли до­пус­ка­ет­ся раз­бие­ние вер­шин мно­же­ст­ва $V$ на два под­мно­же­ст­ва $V_1$ и $V_2$, со­стоя­щие из по­пар­но не­смеж­ных вер­шин, та­кой граф обо­зна­ча­ет­ся , где $n_i$ – чис­ло вер­шин в под­мно­же­ст­ве $V_i, i=1, 2$.

Зна­чит. часть ис­сле­до­ва­ний в Г. т. со­став­ля­ют пе­ре­чис­ли­тель­ные и экс­тре­маль­ные за­да­чи. Отд. класс экс­тре­маль­ных за­дач – за­да­чи о по­кры­тии. Осн. объ­ек­та­ми ис­сле­до­ва­ния в за­да­чах о по­кры­тии яв­ля­ют­ся че­ты­ре важ­ней­шие тео­ре­ти­ко-гра­фо­вые кон­стан­ты: чис­ло вер­шин­но­го по­кры­тия $α_0$, чис­ло рё­бер­но­го по­кры­тия $α_1$, вер­шин­ное чис­ло не­за­ви­си­мо­сти $β_0$ и рё­бер­ное чис­ло не­за­ви­си­мо­сти $β_1$. Чис­ло вер­шин­но­го по­кры­тия гра­фа $G$ есть ми­ним. чис­ло вер­шин в по­кры­ваю­щем мно­же­ст­ве, т. е. в та­ком мно­же­ст­ве вер­шин, для ко­то­ро­го ка­ж­дое реб­ро гра­фа $G$ ин­ци­дент­но хо­тя бы од­ной вер­ши­не это­го мно­же­ст­ва. Вер­шин­ное чис­ло не­за­ви­си­мо­сти гра­фа $G$ есть наи­боль­шее воз­мож­ное чис­ло эле­мен­тов в не­за­ви­си­мом мно­же­ст­ве, т. е. в та­ком мно­же­ст­ве вер­шин, в ко­то­ром лю­бые две вер­ши­ны несмеж­ны. Ана­ло­гич­но оп­ре­де­ля­ют­ся чис­ло рё­бер­но­го по­кры­тия и рё­бер­ное чис­ло не­за­ви­си­мо­сти. Для лю­бо­го связ­но­го гра­фа $G$ с $p>1$ вер­ши­на­ми $α_0+β_0=α_1+β_1=p$, а для дву­доль­но­го гра­фа $β_1=α_0$. Зна­че­ния этих кон­стант из­вест­ны лишь для не­ко­то­рых гра­фов ча­ст­но­го ви­да. К за­да­чам о по­кры­тии тес­но при­мы­ка­ет тео­рия до­ми­ни­ро­ва­ния. В ней рас­смат­ри­ва­ют­ся до­ми­ни­рую­щие мно­же­ст­ва гра­фа $G=(V, E)$, т. е. та­кие под­мно­же­ст­ва $D \subset V$, что лю­бая вер­ши­на из $V\setminus D$ смеж­на хо­тя бы с од­ной из вер­шин $D$. Важ­ней­шей кон­стан­той гра­фа яв­ля­ет­ся чис­ло до­ми­ни­ро­ва­ния – наи­мень­шее воз­мож­ное чис­ло вер­шин в его до­ми­ни­рую­щем мно­же­ст­ве.

Лит.: König D. Theorie der endlichen und unendlichen Graphen. N. Y., 1950; Берж К. Тео­рия гра­фов и ее при­ме­не­ние. М., 1962; Зы­ков А. А. Тео­рия ко­неч­ных гра­фов. Но­во­сиб., 1969; Ха­ра­ри Ф. Тео­рия гра­фов. М., 1973; Ба­са­кер Р., Саа­ти Т. Ко­неч­ные гра­фы и се­ти. М., 1974; Ка­ме­рон П., Линт Д. Тео­рия гра­фов, тео­рия ко­ди­ро­ва­ния и блок-схе­мы. М., 1980; Оре О. Тео­рия гра­фов. 2-е изд. М., 1980; Цвет­ко­вич Д., Дуб М., Закс Х. Спек­тры гра­фов. Тео­рия и при­ме­не­ние. К., 1984; Сач­ков В. Н., Та­ра­ка­нов В. Е. Ком­би­на­то­ри­ка не­от­ри­ца­тель­ных мат­риц. М., 2000; Кол­чин В. Ф. Слу­чай­ные гра­фы. 2-е изд. М., 2004; Сач­ков В. Н. Вве­де­ние в ком­би­на­тор­ные ме­то­ды дис­крет­ной ма­те­ма­ти­ки. 2-е изд. М., 2004.

Вернуться к началу