ГДЗ по информатике, 11 класс, Босова, номер p147.10

Для выполнения задания необходимо дать четкие определения основным типам графов и привести соответствующие примеры. Мы будем опираться на стандартную терминологию теории графов, используемую в курсе информатики.

1. Граф

Определение: Граф — это математическая структура, состоящая из множества вершин (узлов) и множества ребер (связей), соединяющих пары вершин. Ребра могут быть направлены или ненаправлены.

Пример: Любая схема связей между объектами, например, карта метрополитена, где станции — это вершины, а пути между ними — ребра.

2. Неориентированный граф

Определение: Неориентированный граф — это граф, в котором ребра не имеют направления. Связь между двумя вершинами симметрична: если есть ребро между A и B, то можно перейти как из A в B, так и из B в A.

Пример: Схема дорог между городами, где движение разрешено в обе стороны по одному и тому же участку трассы.

3. Ориентированный граф (орграф)

Определение: Ориентированный граф — это граф, в котором каждое ребро имеет направление (называется дугой). Переход возможен только в направлении стрелки: из начальной вершины дуги в конечную.

Пример: Карта односторонних улиц в городе или схема потоков данных в компьютерной сети, где пакеты передаются строго от отправителя к получателю.

4. Взвешенный граф

Определение: Взвешенный граф — это граф (ориентированный или неориентированный), каждому ребру которого сопоставлено числовое значение, называемое весом. Вес может обозначать расстояние, стоимость, время прохождения и т.д.

Пример: Карта автомобильных дорог с указанием расстояния в километрах между перекрестками или авиационная маршрутная сеть с указанием стоимости билета между аэропортами.