ВУЗ:
Составители:
15
полуматрицы: положительную и отрицательную.
Чтобы окончательно определиться с понятием «граф», необходимо
освоить ряд определений.
Подграфом G
А
графа G называется граф, в который входит лишь часть
вершин графа G, образующих множество А вместе с дугами, соединяющими
эти вершины (рис. 2, б).
Частичным графом G
A
по отношению к графу G называется граф,
содержащий только часть дуг графа G (рис. 2, в).
Следует помнить, что при ответе на этот вопрос необходимо давать
математическую интерпретацию определений с графическим пояснением.
Помимо дуги, другими важными понятиями являются понятия пути и
контура. Путем в графе называется така я последовательность дуг, в которой
конец каждой
предыдущей дуги совпадает с началом следующей. Пу ть может
быть конечным и бесконечным. Путь, в котором никакая дуга не встречается
дважды, называется простым (рис. 2, г). Путь, в котором никакая вершина не
встречается дважды, называется элементарным (рис. 2, д). Контур – это
конечный путь, у которого начальная вершина совпадает с конечной ((с, е),
(е, d), (d,
с) на рис. 2, а). Контур называется элементарным, ес ли все его
вершины различны (за исключением начальной и конечной, которые
совпадают). Контур единичной длины, образованный дугой вида (а, а),
называется петлей (см. рис. 2, а).
Иногда граф рассматривают без учета ориентации его дуг. В этом случае
его называют неориентированным и для него понятия «дуга
», «путь» и
«контур» заменяются понятиями «ребро», «цепь», «цикл». Ребро – это отрезок,
соединяющий две вершины. Цепь – это последовательность ребер, а циклом
называют конечную цепь, у которой начальная и конечная вершины совпадают.
Частным случаем неориентированного графа является дерево – конечный
связный неориентированный граф, не имеющий циклов (рис. 2, е).
Граф дает удобное геометрическое представление
отношений на
множестве, поэтому теория графов и теория отношений на множестве взаимно
дополняют друг друга. Если для любых двух вершин х и у, удовлетворяющих
условию х ≠ у, существует путь из х в у, то считают, что на графе G = (X, Г)
введено отношение порядка. Кроме того, вершины, лежащие на одном контуре,
являются эквивалентными, т. е. на графе вводится отношение эквивалентности.
Отношение порядка и отношение эквивалентности отражают на графе свойства
рефлексивности, транзитивнос ти и антисимметричности.
В практических приложениях имеет большое значение задача о
нахождении кратчайшего пути между двумя вершинами связного
неориентированного графа. Каждому ребру такого графа приписано некоторое
число λ(u) ≥ 0, которое может быть расстоянием между объектами, временем,
стоимостью перевозки груза по этому ребру и т. п. Иногда приходится иметь
дело с графами, ребра которых имеют
одинаковую длину, принимаемую за
единицу. Вершины такого графа представляют собой состояния некоторой
системы, в которой все переходы, делаемые за один шаг, эквивалентны.
Страницы
- « первая
- ‹ предыдущая
- …
- 14
- 15
- 16
- 17
- 18
- …
- следующая ›
- последняя »
