Задача 1. Для графа G указать вершины, ребра, изолированные вершины, кратные ребра, петли.
x 3 
|
| x 5
|
| x 2
|
Задача 2. Для графа Д указать вершины, дуги, петли.
| x 3
|
| x 2
|
| x 5
|
Задача 3. Задан орграф G2. Указать вершины, дуги. У дуги х 3 начальную и конечную вершины. Какая из дуг является петлей?
Задача 4. Для графа G привести примеры маршрута, замкнутого маршрута, простой цепи, цикла, простого цикла.
v 6 
|
| v 5
|
Задача 5. Представить карту Брянской области в виде плоского графа (вершины – районы, ребра – границы).
Задача 6. Сколько существует простых путей из левой нижней в правую верхнюю вершину в данном графе?
Понятие связности, смежности и инцидентности
Если в графе любые две вершины можно соединить цепью, то граф называется связным. В противном случае он несвязный.
Связный граф, не содержащий циклов, называется деревом. Несвязный граф распадается на непересекающиеся максимальные связные компоненты (связные подграфы).
Вершины vi, vi+ 1, соединенные между собой ребром (дугой), называются смежными. Таким образом, смежность это отношение между вершинами.
С другой стороны, вершины vi, vi+ 1 инцидентны ребру (дуги), которым они связаны.
Таким образом, инцидентность характеризует отношение между ребрами и вершинами. Ребро (дуга) инцидентно каждой вершине, которую оно соединяет. В результате можно сделать вывод, что граф задает два основных отношения: смежности и инцидентности. Степень вершины графа – число ребер, инцидентных ей. Если степень вершины графа равна 1, то она называется висячей. Если степень вершины графа равна 0, то она называется изолированной.
Пусть дан граф G с вершинами v 1,…, v n и ребрами х 1,…, хm.
Матрица смежности графа G – это квадратная матрица А(G) размера n x n (n – число вершин) с элементами
Матрица смежности графа G обладает свойством симметрии. Она показывает, существует ли путь длины 1 из вершины v i в вершину v j. Также можно получить информацию о путях большей длины. Для этого необходимо возвести матрицу смежности в нужную степень. m – степень матрицы смежности Аm, заполненная числами аij(m), показывает число путей длины m из i вершины в j.
Дан орграф D с вершинами v 1,…, v n и дугами х 1,…, хm. Матрица смежности орграфа D – это квадратная матрица А(D) размера n x n (n – число вершин) с элементами
Матрица смежности орграфа D свойством симметрии не обладает.
Матрица инцидентности орграфа D – это матрица В(D) размера n x m (n – число вершин, m – число дуг) с элементами
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1. Для графа G перечислить все вершины и ребра, указать степени всех вершин. Какие из них являются висячими, а какие изолированными?
| v 5
|
| v 6
|
3 bnJldi54bWxMj81OwzAQhO9IvIO1SFwq6tRSkxCyqVAlLnAACg/gxEsS4Z8Qu6n79rgnOI5mNPNN vYtGs4VmPzqLsFlnwMh2To22R/j8eLorgfkgrZLaWUI4k4ddc31Vy0q5k32n5RB6lkqsryTCEMJU ce67gYz0azeRTd6Xm40MSc49V7M8pXKjuciynBs52rQwyIn2A3Xfh6NBeH59W51FzFc/xbbdx6XU 8cVrxNub+PgALFAMf2G44Cd0aBJT645WeaYRtkWekghCFMAuvijStxbhflMCb2r+/0DzCwAA//8D AFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9U eXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9y ZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAAFOUeT1AQAA6wMAAA4AAAAAAAAAAAAAAAAALgIAAGRy cy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhAK8SuWHdAAAACAEAAA8AAAAAAAAAAAAAAAAATwQA AGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABZBQAAAAA= " strokecolor="black [3040]"/>
Решение. v 1, v 2, v 3, v 4, v 5, v 6, v 7 – вершины графа G; ребра графа G – х 1, х 2, х 3, х 4, х 5. Вершина v 1 имеет степень 1, так как ей инцидентно только одно ребро х 1. Вершина v 2 имеет степень 4, так как ей инцидентны ребра х 1, х 2, х 4, х 5. Вершина v 3 имеет степень 2, так как ей инцидентны два ребра х 2 и х 3 и т.д. Вершина v 7 имеет степень 0, так как нет ребер ей инцидентных. Таким образом, вершины v 1 и v 6 являются висячими, так как их степень равна 1. Вершина v 7 является изолированной, так как она имеет степень 0.
Задача 2. Для графа G построить матрицу смежности А(G).
| v 5
|
Решение. Так как у графа 5 вершин, то размер матрицы А(G) будет 5х5. Так как вершины v 1и v 2 связаны ребром х 1, то а 12=1, так как вершины v 1 и v 3 связаны ребром х 2, то а 13=1, и т.д. В результате получаем матрицу смежности А(G):
Заметим, что матрица смежности А(G) обладает свойством симметрии.
Задача 3. Пусть дан орграф D. Записать для графа D матрицу смежности А(D) и матрицу инцидентности В(D).
| v 6
|
| v 5
|
Решение. Орграф D содержит 6 вершин и 7 дуг, поэтому размер матрицы А(D) будет 6х6, а матрица В(D) – 6х7. Так как орграф D не содержит дуги из v 1 в v 1 (петли), то а 11=0. Так как орграф D не содержит дуги из v 1 в v 2, то а 12=0. Так как из вершины v 1 в вершину v 3 существует дуга х 2, то а 13=1 и т.д.
В результате получаем матрицу инцидентности А(D):
Матрица смежности А(D) орграфа D не обладает свойством симметрии.
Составим матрицу инцидентности В(D) орграфа D. Элемент b 11=-1, так как в вершине v 1 заканчивается дуга х 1;
элемент b 12=1, так как в вершине v 1 заканчивается дуга х 2 и т.д. В результате получаем матрицу инцидентности В(D):
Задача 4. Пусть дан граф G. Определить количество путей длины 3 из вершины v 2 в вершину v 5.
| v 5
|
Решение. Составим матрицу смежности графа G. Так как вершин у графа G равно 5, то матрица смежности имеет размерность 5х5.
Так как необходимо определить пути длины 3, то матрицу смежности возведем в 3-ю степень.
Так как элемент а 25=1, то из вершины v 2 в вершину v 5 существует один путь длины 3, а именно х 2 х 4 х 6.
