Основные понятия теории графов. Гладких О.Б - 24 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

24
Определение 1.24. Число дуг пути называется
длиной пути.
Определение 1.25. Путь называется контуром, ес-
ли его начальная вершина совпадает с конечной
вершиной
.
Определение 1.26. Путь (контур), в котором все
дуги различны, называется
простым.
Определение 1.27. Путь (контур), в котором все
вершины, кроме первой и последней, различны,
называется
элементарным.
Следует усвоить, что понятиям ребра, мар-
шрута, цепи, цикла в неориентированном графе
соответствуют понятия дуги, пути, ориентирован-
ной цепи, контура в ориентированном графе. Для
лучшего запоминания приведем эти термины в
таблице 1.1.
Таблица 1.1.
Неориентированный
граф
Ориентированный
граф
ребро
маршрут
цикл
дуга
путь
контур
Пример 1.13.
В приведенном на рис. 10. графе выделим
следующие пути:
(x
1
,x
2
,x
3
,x
4
) – простой элементарный путь, т.к. каж-
дая вершина и каждая дуга использу-
ются не более одного раза;
153
Теория графов находит применение в раз-
личных областях современной математики и ее
многочисленных приложений, в особенности это
относится к экономике, например, когда надо вы-
брать наилучшие варианты развозки товаров по
магазинам, строительных материалов. При состав-
лении больших проектов, содержащих различные
виды работ, часто возникает ситуация, когда ту
или иную работу можно начать лишь по оконча-
нии других. Так, при строительстве дома нельзя
приступить к отделочным работам, пока не возве-
дены стены, и нельзя возводить стены до укладки
фундамента. Последовательность работ изобража-
ется в виде сетевых графиков. Они применяются
при планировании деятельности предприятия.
Например, зная дату начала строительства и
время, необходимое для выполнения каждой рабо-
ты, можно выяснить, к какому сроку следует под-
везти материалы или пригласить бригады специа-
листов: плотников, маляров, электриков и т. д.
Сетевые графики используют не только
строители, но и конструкторы машин с большим
количеством узлов и деталей, диспетчеры желез-
ных дорог и многие другие специалисты.
Рассмотрим применение графа в строитель-
стве (рис. 6.2). 
Определение 1.24. Число дуг пути называется                  Теория графов находит применение в раз-
длиной пути.                                           личных областях современной математики и ее
Определение 1.25. Путь называется контуром, ес-        многочисленных приложений, в особенности это
ли его начальная вершина совпадает с конечной          относится к экономике, например, когда надо вы-
вершиной.                                              брать наилучшие варианты развозки товаров по
Определение 1.26. Путь (контур), в котором все         магазинам, строительных материалов. При состав-
дуги различны, называется простым.                     лении больших проектов, содержащих различные
Определение 1.27. Путь (контур), в котором все         виды работ, часто возникает ситуация, когда ту
вершины, кроме первой и последней, различны,           или иную работу можно начать лишь по оконча-
называется элементарным.                               нии других. Так, при строительстве дома нельзя
      Следует усвоить, что понятиям ребра, мар-        приступить к отделочным работам, пока не возве-
шрута, цепи, цикла в неориентированном графе           дены стены, и нельзя возводить стены до укладки
соответствуют понятия дуги, пути, ориентирован-        фундамента. Последовательность работ изобража-
ной цепи, контура в ориентированном графе. Для         ется в виде сетевых графиков. Они применяются
лучшего запоминания приведем эти термины в             при планировании деятельности предприятия.
таблице 1.1.                                                 Например, зная дату начала строительства и
                                       Таблица 1.1.    время, необходимое для выполнения каждой рабо-
        Неориентированный Ориентированный              ты, можно выяснить, к какому сроку следует под-
               граф             граф                   везти материалы или пригласить бригады специа-
             ребро             дуга
             маршрут           путь                    листов: плотников, маляров, электриков и т. д.
             цикл              контур                        Сетевые графики используют не только
                                                       строители, но и конструкторы машин с большим
                         Пример 1.13.                  количеством узлов и деталей, диспетчеры желез-
       В приведенном на рис. 10. графе выделим         ных дорог и многие другие специалисты.
следующие пути:                                              Рассмотрим применение графа в строитель-
(x1,x2,x3,x4) – простой элементарный путь, т.к. каж-   стве (рис. 6.2).
                дая вершина и каждая дуга использу-
                ются не более одного раза;


                           24                                                   153

Страницы