Математика. Быкадорова Г.В. - 49 стр.

                                          49
6.22.     Для заданного бинарного отношения Р и множества Х найти
        область определения и область значений Р, обратное к Р отношение,
        образ и прообраз множества Х относительно отношения Р:
        а) Р={(1,3), (1,4), (3,4), (3,6), (1,6), (4,2), (4,6), (0,5), (2,6)} и Х={1};
        б) Р={(0,2), (1,2), (0,4), (3,4), (3,7), (2,4), (3,6), (2,7), (0,6)} и Х={0};
        в) Р={(2,3), (2,5), (2,7), (4,3), (4,5), (4,7), (8,3), (8,5), (8,7)} и Х={4}.
                      6.4. Основные понятия теории графов
      Графы представляют собой наиболее абстрактную структуру, с
которой приходится сталкиваться в теории ЭВМ. Графы используются для
описания алгоритмов автоматического проектирования, в диаграммах
машин конечных состояний, при решении задач маршрутизации потоков и
т.д. Любая система, предполагающая наличие дискретных состояний,
объектов или наличие узлов и переходов между ними, может быть
описана графом.
          2 ●                    Объекты    в   графах   называются
                    3       вершинами и отмечаются точками, а связи
                            между ними называются         дугами и
                      ●
                            отмечаются        стрелками         между
  1●                        соответствующими точками (рис.6.5).
                                 Граф может изображать сеть улиц в
                  ●         городе: вершины графа – перекрестки, а
                    4
                            дуги – улицы с разрешенным направлением
   Рис. 6.5. Изображение    движения.
           графа.
Определение. Графом G = M ; R называется пара двух конечных
множеств: множество М точек и множество R линий, соединяющих
некоторые пары точек.
        Элементы множества М называются вершинами или узлами графа G,
а элементы бинарного отношения R ⊆ M 2 - дугами. Таком образом, дугами
являются пары вершин (a, b )∈R . При этом дуга (a, b ) называется
исходящей из вершины а и заходящей в вершину b.
       Изображение графа G = M ; R получается путем расположения
различных точек на плоскости для каждой вершины a ∈M , причем, если
(a, b )∈R , то проводится стрелка (дуга) из вершины а в вершину b.
Пример 6.16. Изобразить граф G = M ; R с                         2
    множеством вершин                        M ={1, 2, 3, 4} и     ●

    множеством дуг                                                    3
    R ={(1, 1), (1, 2 ), (2, 3), (3, 4 ), (4, 3), (4, 1)}.     1     ●
                                                               ●
        Решение.
                                                                             ●
                                                                                 4