Решить

Привет! Давай разбираться с этими утверждениями о графах.

1. В графе могут быть вершины, между которыми нет пути. Это утверждение верно, так как граф может быть несвязным, и в этом случае между некоторыми из его вершин не будет пути.

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

3. Дерево это всегда связный граф. Это верно. Дерево — это связный граф без циклов, в котором есть ровно один путь между любыми двумя его вершинами.

4. Матрица смежности неориентированного графа не всегда симметрична относительно главной диагонали. Это неверно, потому что матрица смежности неориентированного графа всегда симметрична относительно главной диагонали, так как наличие ребра между вершинами \( i \) и \( j \) подразумевает наличие ребра между \( j \) и \( i \).

Итак, отмечаем правильные утверждения:

• В графе могут быть вершины, между которы