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

UptoLike

ВУЗ: 

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

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

Рубрика: 

10
Существуют два основных вида графов (и
множество их подвидов): ориентированные и не-
ориентированные.
Если ребрам графа приданы направления от
одной вершины к другой, то такой граф называет-
ся ориентированным. Ребра ориентированного
графа называются дугами. Соответствующие вер-
шины ориентированного графа называют началом
и концом. Если направления ребер не указывают-
ся, то граф называется неориентированным (или
просто графом).
Теория графов многократно переоткрыва-
лась разными авторами при решении различных
прикладных задач. Например, задача о Кёнигс-
бергских мостах.
На рис. 1 представлен схематический план
Рис. 1. Схематический план города и его представление в
виде графа.
A
C
B
D
167
4.4.
4.5.
5. Определить минимальное число часовых, необ-
ходимых для охраны 11 объектов, расположенных
в вершинах графа. Объекты просматриваются по
ребрам графа. 
      Существуют два основных вида графов (и              4.4.
множество их подвидов): ориентированные и не-
ориентированные.
      Если ребрам графа приданы направления от
одной вершины к другой, то такой граф называет-
ся ориентированным. Ребра ориентированного
графа называются дугами. Соответствующие вер-
шины ориентированного графа называют началом              4.5.
и концом. Если направления ребер не указывают-
ся, то граф называется неориентированным (или
просто графом).
      Теория графов многократно переоткрыва-
лась разными авторами при решении различных
прикладных задач. Например, задача о Кёнигс-
бергских мостах.
      На рис. 1 представлен схематический план            5. Определить минимальное число часовых, необ-
                                                          ходимых для охраны 11 объектов, расположенных
      C                                                   в вершинах графа. Объекты просматриваются по
                                                          ребрам графа.

      A          D


      B


Рис. 1. Схематический план города и его представление в
                      виде графа.


                             10                                                   167

Страницы