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

  Ñîäåðæàíèå
  Ïðåäèñëîâèå                                                                                                 3
1. Ââåäåíèå                                                                                                    5
  1.1.   Îïðåäåëåíèå ãðàôà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             5
  1.2.   Ïîäãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   10
  1.3.   Âèäû ãðàôîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      13
  1.4.   Ìàòðèöû ãðàôîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           18
  1.5.   Äèàìåòð, ðàäèóñ è öåíòð ãðàôà . . . . . . . . . . . . . . . . . . . . . . .                          22
  1.6.   Îðèåíòèðîâàííûå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                    23
  1.7.   Ìàðøðóòû, öåïè è ïðîñòûå öåïè . . . . . . . . . . . . . . . . . . . . . .                            30

2. Ñâÿçíîñòü â îðãðàôàõ                                                                                       31
  2.1.   Îñíîâíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           31
  2.2.   Êîìïîíåíòû ñâÿçíîñòè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                 32
  2.3.   Êîíäåíñàöèÿ îðãðàôà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                33
  2.4.   Îòûñêàíèå ñèëüíûõ êîìïîíåíò . . . . . . . . . . . . . . . . . . . . . . . .                          33
  2.5.   Ìàòðèöû äîñòèæèìîñòåé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                    36
  2.6.   Ïîëó÷åíèå ìàòðèöû äîñòèæèìîñòåé. . . . . . . . . . . . . . . . . . .                                 38
  2.7.   Àëãîðèòì Óîðøîëëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .              39
  2.8.   Áàçà ãðàôà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   41

3. Äåðåâüÿ                                                                                                    43
  3.1. Îñíîâíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             43
  3.2. Îïèñàíèå äåðåâüåâ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             46
  3.3. Çàäà÷è ñ äåðåâüÿìè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .               50
       3.3.1. Ïåðå÷èñëåíèå îñòîâíûõ äåðåâüåâ . . . . . . . . . . . . . . .                                    50
       3.3.2. Ïåðåñ÷åò îñòîâíûõ äåðåâüåâ . . . . . . . . . . . . . . . . . . . .                              53
  3.4. Çàäà÷à î êðàò÷àéøåì îñòîâå ãðàôà . . . . . . . . . . . . . . . . . . .                                 56
       3.4.1. Àëãîðèòì Êðàñêàëà . . . . . . . . . . . . . . . . . . . . . . . . . . . .                       56
       3.4.2. Àëãîðèòì Ïðèìà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                    63



                                                  143