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