Привет! Сегодня наша тема посвящена графам. В ЕГЭ по информатике есть два задания по этой теме. Задание №1 - соотнесение таблицы и графа. Его мы уже разобрали тут. И задание №13 - поиск путей в графе. Но для начала пройдемся по основным определениям.
Граф - это один из способов представления в информации. Граф включает в себя множество точек - вершин, и множество линий соединяющих эти точки - ребер.
Путь в графе - последовательность вершин, каждая из которых, кроме последней, соединена со следующей - ребром.
Длиной пути в графе называется количество(длина) ребер, составляющих этот путь.
Маршрут в графе - это тот же путь, только он не требует последовательности разных вершин.
Цикл - группа вершин, связанных вместе в замкнутую цепь. Вершина в цикле являющаяся его началом, является и его концом.
Связный граф - граф, в котором между любой парой вершин имеется один путь.
Дерево - связный граф, не содержащий цикла.
Неориентированный граф - граф, в котором ребра не имеют направления.
Ориентированный граф - граф, в котором ребра имеют направление и обозначаются стрелками.
Степень вершины - количество ребер, концом которых она является.
Понравилась статья? Ставьте пальцы вверх и подписывайтесь, чтобы не пропустить другие наши материалы.