Элементы теории графов. Домнин Л.Н. - 144 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

4. Ïóòè è ìàðøðóòû â ãðàôàõ                                                                               70
     4.1.    Ñóùåñòâîâàíèå ïóòåé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       70
     4.2.    Ïåðåñ÷åò ìàðøðóòîâ è ïóòåé . . . . . . . . . . . . . . . . . . . . . . . . . .                71
     4.3.    Ïåðå÷èñëåíèå ìàðøðóòîâ è ïóòåé . . . . . . . . . . . . . . . . . . . . .                      73
     4.4.    Çàäà÷è î êðàò÷àéøèõ ïóòÿõ . . . . . . . . . . . . . . . . . . . . . . . . . . .               75
             4.4.1. Ãðàôû ñ äóãàìè åäèíè÷íîé äëèíû . . . . . . . . . . . . .                               77
             4.4.2. Ãðàôû ñî âçâåøåííûìè äóãàìè (ðåáðàìè) . . . . .                                        81
             4.4.3. Àöèêëè÷åñêèå îðãðàôû . . . . . . . . . . . . . . . . . . . . . . . .                   92

5. Öèêëû                                                                                                  98
     5.1. Ôóíäàìåíòàëüíûå öèêëû è ðàçðåçû . . . . . . . . . . . . . . . . . . . 98
     5.2. Ýéëåðîâû öèêëû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
          5.2.1. Îïðåäåëåíèå è óñëîâèÿ ñóùåñòâîâàíèÿ . . . . . . . . . 102
          5.2.2. Àëãîðèòì ïîèñêà ýéëåðîâà öèêëà . . . . . . . . . . . . . . 105
          5.2.3. Î êîëè÷åñòâå ýéëåðîâûõ ãðàôîâ . . . . . . . . . . . . . . . 108
          5.2.4. Çàäà÷à ïî÷òàëüîíà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
     5.3. Ãàìèëüòîíîâû öèêëû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
          5.3.1. Îïðåäåëåíèå è óñëîâèÿ ñóùåñòâîâàíèÿ . . . . . . . . . 112
          5.3.2. Ìåòîäû ïîèñêà ãàìèëüòîíîâûõ öèêëîâ . . . . . . . . . 116
     5.4. Çàäà÷à êîììèâîÿæåðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
          5.4.1. Ïðèìåíåíèå è ìåòîäû ðåøåíèÿ çàäà÷è . . . . . . . . . 127
          5.4.2. Ìåòîä âåòâåé è ãðàíèö . . . . . . . . . . . . . . . . . . . . . . . . . 128

Ñïèñîê ëèòåðàòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

Óêàçàòåëü îáîçíà÷åíèé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

Ïðåäìåòíûé óêàçàòåëü . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142




                                                    144

Страницы