Задачи для самостоятельного решения

 Задача 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

 

    Решение. 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, а именно х ₂ х ₄ х ₆.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: