43. Маршруты, цепи, циклы.

Маршрутом в графе G называется такая последовательность (конечная или бесконечная) ребер (e1,e2,…,en), что каждые 2 соседних ребра в этой последовательности имеют общую вершину.

Одно и то же ребро в маршруте может встречаться несколько раз.

Маршрут называется открытым, если начальная и конечная вершины его различны. Иначе – замкнутым.

Число ребер определяет его длину.

Если начальная вершина и конечная вершина маршрута совпадает, то маршрут называется циклическим.

Маршрут называется цепью, если каждое ребро встречается не более одного раза и простой цепью, если любая вершина инцидента не более, чем 2 ребрам.

Циклический маршрут называют циклом, если он является цепью и простым циклом, если он является простой цепью.

44.Связные компоненты графа.

Две вершины Vi Vj называют связными в графе G если в нем сущ маршрут, в котором

Vi и Vj являются началом и концом. Граф G называется связным, если каждая пара его вершин явл связной, иначе — несвязный.

Если вершина V э G связана с какой-то другой вершиной графа G , то она явл связанной с само собой. Отношением связности заданное на графе явл рефлексивным, симметричным и транзитивным. Док-во: 1.) мы можем начинать маршрут в вершине Vi и заканчивать его в этой же вершине: A Vi R Vi – св-во транзитивности.2.)Vi R Vj, Vj R Vi — св-во симметричности, мы можем проходить маршрут по и против часовой стрелки. 3.) Пусть сущ Vс: Vi R Vс, Vс R Vi =) Vi R Vj, т. к. граф связный, то каждая пара его вершин явл связными., т. е. Это св-во выполняется.

Отношение связности явл отношением эквивалентности, а =) определяет разбиение мн-ва вершин графа на непересекающиеся подмн-ва Vi. Вершины одного и того же подмн-ва Vi связаны друг с другом, а вершины подмножеств Vi и Vj не связанны между собой, поэтому в графе G нет ребер с разными концами в мн-вах Vi и Vj и граф G может быть розложен в прямую сумму частей графа G = iV G (Vi)

45.Расстояния.

Пусть задан граф G — связный, неориентированный. Vi Vj — любые его две вершины. В графе сущ связывающие эти две вершины простая цепь М(е1,е2,е3...ед). Если кол-во ребер в этой цепи не явл минимальным из возможных, то сущ цепь М'(е'1,е'2,е'3...е'д) и если M' не явл минимальным, то млжно найти цнпь с еще меньшим кол-вом ребер и процесс уменьшения кол-ва ребер можно повторить несколько раз. В графе всегда можно найти цепь связывающую вершины Vi и Vj такую, которая будет иметь минимальное кол-во ребер р. Минимальная длина простой цепи связывающей вершину Vi и Vj называется расстоянием d. Если считать в связном графе, что вершина V связана сама собой, то можно определить нулевой маршрут. Расстояние между вершиной V и ею самой =0. Для любых двух вершин Vi и Vj d >0, т. к. сущ цепь связывающая эти вершины и состаящая хотя бы из одного ребра.

d(Vi, Vj) - расстояние между вершинами удовл следующим аксиомам метрики:

1. d(Vi, Vj) >0 , d(Vi, Vj) = 0 только в том случае, если вершины Vi, Vj совпадают

2. d(Vi, Vj) = d(Vj, Vi)

3. d(Vi, Vc) + d(Vc, Vj) >= d(Vi, Vc) Неравенство треугольника.