Задачи для самостоятельного решения. Задача 1. Для графа g указать вершины, ребра, изолированные вершины, кратные ребра, петли

Задача 1. Для графа G указать вершины, ребра, изолированные вершины, кратные ребра, петли.

x 4

v 1

x 3

x 5

x 2

v 4

v 3

v 5

x 1

v 2

 

Задача 2. Для графа Д указать вершины, дуги, петли.

v 2

x 4

x 1

x 3

x 2

v 4

v 3

x 5

v 1

 

Задача 3. Задан орграф G₂. Указать вершины, дуги. У дуги х ₃ начальную и конечную вершины. Какая из дуг является петлей?

x 7

x 6

x 5

x 4

x 3

x 2

x 1

v 5

v 4

v 3

v 2

v 1

 

 

 

Задача 4. Для графа G привести примеры маршрута, замкнутого маршрута, простой цепи, цикла, простого цикла.

 

v 6

v 5

v 4

v 3

v 2

v 1

x 8

x 6

x 7

x 5

x 3

x 4

x 2

x 1

 

Задача 5. Представить карту Брянской области в виде плоского графа (вершины – районы, ребра – границы).

Задача 6. Сколько существует простых путей из левой нижней в правую верхнюю вершину в данном графе?

 

 

Понятие связности, смежности и инцидентности

 

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

Связный граф, не содержащий циклов, называется деревом. Несвязный граф распадается на непересекающиеся максимальные связные компоненты (связные подграфы).

Вершины v_i, v_{i+ 1}, соединенные между собой ребром (дугой), называются смежными. Таким образом, смежность это отношение между вершинами.

С другой стороны, вершины v_i, v_{i+ 1} инцидентны ребру (дуги), которым они связаны.

Таким образом, инцидентность характеризует отношение между ребрами и вершинами. Ребро (дуга) инцидентно каждой вершине, которую оно соединяет. В результате можно сделать вывод, что граф задает два основных отношения: смежности и инцидентности. Степень вершины графа – число ребер, инцидентных ей. Если степень вершины графа равна 1, то она называется висячей. Если степень вершины графа равна 0, то она называется изолированной.

Пусть дан граф G с вершинами v ₁,…, v _n и ребрами х ₁,…, х_m.

Матрица смежности графа G – это квадратная матрица А(G) размера n x n (n – число вершин) с элементами

Матрица смежности графа G обладает свойством симметрии. Она показывает, существует ли путь длины 1 из вершины v _i в вершину v _j. Также можно получить информацию о путях большей длины. Для этого необходимо возвести матрицу смежности в нужную степень. m – степень матрицы смежности А^m, заполненная числами а_ij^(m), показывает число путей длины m из i вершины в j.

Дан орграф D с вершинами v ₁,…, v _n и дугами х ₁,…, х_m. Матрица смежности орграфа D – это квадратная матрица А(D) размера n x n (n – число вершин) с элементами

Матрица смежности орграфа D свойством симметрии не обладает.

Матрица инцидентности орграфа D – это матрица В(D) размера n x m (n – число вершин, m – число дуг) с элементами

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1. Для графа G перечислить все вершины и ребра, указать степени всех вершин. Какие из них являются висячими, а какие изолированными?

v 5

v 6

v 4

v 3

v 2

v 1

x 6

x 5

x 3

x 4

x 2

x 1

3 bnJldi54bWxMj81OwzAQhO9IvIO1SFwq6tRSkxCyqVAlLnAACg/gxEsS4Z8Qu6n79rgnOI5mNPNN vYtGs4VmPzqLsFlnwMh2To22R/j8eLorgfkgrZLaWUI4k4ddc31Vy0q5k32n5RB6lkqsryTCEMJU ce67gYz0azeRTd6Xm40MSc49V7M8pXKjuciynBs52rQwyIn2A3Xfh6NBeH59W51FzFc/xbbdx6XU 8cVrxNub+PgALFAMf2G44Cd0aBJT645WeaYRtkWekghCFMAuvijStxbhflMCb2r+/0DzCwAA//8D AFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9U eXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9y ZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAAFOUeT1AQAA6wMAAA4AAAAAAAAAAAAAAAAALgIAAGRy cy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhAK8SuWHdAAAACAEAAA8AAAAAAAAAAAAAAAAATwQA AGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABZBQAAAAA= " strokecolor="black [3040]"/>

 

Решение. v ₁, v ₂, v ₃, v ₄, v ₅, v ₆, v ₇ – вершины графа G; ребра графа G – х ₁, х ₂, х ₃, х ₄, х ₅. Вершина v ₁ имеет степень 1, так как ей инцидентно только одно ребро х ₁. Вершина v ₂ имеет степень 4, так как ей инцидентны ребра х ₁, х ₂, х ₄, х ₅. Вершина v ₃ имеет степень 2, так как ей инцидентны два ребра х ₂ и х ₃ и т.д. Вершина v ₇ имеет степень 0, так как нет ребер ей инцидентных. Таким образом, вершины v ₁ и v ₆ являются висячими, так как их степень равна 1. Вершина v ₇ является изолированной, так как она имеет степень 0.

Задача 2. Для графа G построить матрицу смежности А(G).

v 5

v 4

v 3

v 2

v 1

x 6

x 5

x 3

x 4

x 2

x 1

 

Решение. Так как у графа 5 вершин, то размер матрицы А(G) будет 5х5. Так как вершины v ₁и v ₂ связаны ребром х ₁, то а ₁₂=1, так как вершины v ₁ и v ₃ связаны ребром х ₂, то а ₁₃=1, и т.д. В результате получаем матрицу смежности А(G):

 

Заметим, что матрица смежности А(G) обладает свойством симметрии.

Задача 3. Пусть дан орграф D. Записать для графа D матрицу смежности А(D) и матрицу инцидентности В(D).

x 6

x 7

v 6

v 2

v 5

v 4

v 3

v 1

x 5

x 3

x 4

x 2

x 1

 

Решение. Орграф D содержит 6 вершин и 7 дуг, поэтому размер матрицы А(D) будет 6х6, а матрица В(D) – 6х7. Так как орграф D не содержит дуги из v ₁ в v ₁ (петли), то а ₁₁=0. Так как орграф D не содержит дуги из v ₁ в v ₂, то а ₁₂=0. Так как из вершины v ₁ в вершину v ₃ существует дуга х ₂, то а ₁₃=1 и т.д.

В результате получаем матрицу инцидентности А(D):

Матрица смежности А(D) орграфа D не обладает свойством симметрии.

Составим матрицу инцидентности В(D) орграфа D. Элемент b ₁₁=-1, так как в вершине v ₁ заканчивается дуга х ₁;

элемент b ₁₂=1, так как в вершине v ₁ заканчивается дуга х ₂ и т.д. В результате получаем матрицу инцидентности В(D):

Задача 4. Пусть дан граф G. Определить количество путей длины 3 из вершины v ₂ в вершину v ₅.

x 78

v 2

x 6

x 7

v 5

v 4

v 3

v 1

x 5

x 3

x 4

x 2

x 1

 

 

Решение. Составим матрицу смежности графа G. Так как вершин у графа G равно 5, то матрица смежности имеет размерность 5х5.

Так как необходимо определить пути длины 3, то матрицу смежности возведем в 3-ю степень.

Так как элемент а ₂₅=1, то из вершины v ₂ в вершину v ₅ существует один путь длины 3, а именно х ₂ х ₄ х ₆.