Page 107 - 4204
P. 107

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

                        Степенем  вершини  називається  кількість  ребер,  що  вихо-


                  дить з вершини.

                        Маршрутом (або шляхом) у графі називається послідовність


                  вершин v  і ребер e  така, що кожні два сусідні ребра в цій послі-
                               i
                                            i
                  довності мають спільну вершину e  = (v ,v ), i=1,2,…,k.
                                                                        i
                                                                           i+1
                                                                  i
                        Вершина  v називається  початком  шляху,  а  вершина  v   
                                                                                                      k+1
                                       1
                  кінцем шляху. Всі інші вершини цього шляху називаються про-


                  міжними, або внутрішніми, вершинами.

                        Кількість ребер k у маршруті називається довжиною марш-


                  руту. Кажуть, що цей маршрут з’єднує вершини v  і v  або веде з
                                                                                      1
                                                                                           k+1
                  вершини v  у вершину v .
                                                   k+1
                                1
                        Маршрут, в якому всі ребра попарно різні, називається лан-


                  цюгом. Маршрут,  в  якому  всі  проміжні вершини  попарно різні,

                  називається простим ланцюгом.


                        Маршрут  називається  замкненим  (або  циклічним),  якщо

                  v =  v .  Замкнений  ланцюг  називається  циклом,  а  замкнений
                   1
                           k+1
                  простий ланцюг  простим циклом.

                        Граф,  довільні  дві  вершини  якого  можуть  бути  з’єднані  де-


                  яким маршрутом називається зв’язним. Інакше граф називається

                  незв’язним.


                        Зв’язний граф що немає циклів називається деревом.

                        Покривним деревом називається будь-яке дерево, що містить


                  усі вершини графа.












                                                             106
   102   103   104   105   106   107   108   109   110   111   112