Вопросы к пункту 1 «Определение графа» на странице 51, ГДЗ по алгебре за 10 класс к учебнику Бунимовича вероятность и статистика

Вопросы к пункту 1 «Определение графа».

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

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

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

Схема метрополитена, которая висит в каждом вагоне поезда, — это граф.

Его вершины — станции метро. Его рёбра — перегоны: два кружка на схеме соединены линией тогда и только тогда, когда между этими станциями поезд идёт без промежуточных остановок. Пересадочный узел изображён на схеме двумя вершинами, соединёнными ребром-переходом.

Такой граф решает главную задачу пассажира: по нему видно, как проехать от одной станции к другой и где нужно сделать пересадку.

Ответ: схема метрополитена: её вершины — станции, а рёбра — перегоны между соседними станциями и переходы внутри пересадочного узла.

Возьмём четыре вершины \(a\), \(b\), \(c\), \(d\) и проведём между ними пять рёбер: \(ab\), \(bc\), \(cd\), \(ad\) и \(ac\).

Матрица смежности этого графа содержит 4 строки и 4 столбца, отвечающие вершинам \(a\), \(b\), \(c\), \(d\). На пересечении строки \(x\) и столбца \(y\) стоит 1, если вершины \(x\) и \(y\) соединены ребром, и 0, если не соединены.

\[\begin{array}{c|c|c|c|c} & a & b & c & d \\ \hline a & 0 & 1 & 1 & 1 \\ b & 1 & 0 & 1 & 0 \\ c & 1 & 1 & 0 & 1 \\ d & 1 & 0 & 1 & 0 \end{array}\]

Матрица симметрична относительно диагонали, потому что граф неориентированный. Единиц в ней 10 — вдвое больше числа рёбер, как и должно быть: каждое ребро даёт единицу в двух симметричных клетках.

Ответ: подходит граф с вершинами \(a\), \(b\), \(c\), \(d\) и рёбрами \(ab\), \(ac\), \(ad\), \(bc\), \(cd\); строки его матрицы смежности в порядке \(a\), \(b\), \(c\), \(d\) — это \(0\ 1\ 1\ 1\), затем \(1\ 0\ 1\ 0\), затем \(1\ 1\ 0\ 1\) и \(1\ 0\ 1\ 0\).

У ориентированного графа на каждом ребре указано направление — нарисована стрелка, и двигаться по ребру можно только в эту сторону. У неориентированного графа стрелок нет, каждое ребро проходится в обе стороны.

Если считать рёбра дорогами, а вершины перекрёстками, то неориентированный граф — это дороги с двусторонним движением, а ориентированный — с односторонним.

Различие видно и в матрице смежности. У неориентированного графа она симметрична: клетки, симметричные относительно диагонали, содержат одинаковые значения. У ориентированного графа это уже не так — в клетке строки \(a\) и столбца \(b\) может стоять 1, а в симметричной ей клетке 0.

Ответ: у ориентированного графа на каждом ребре указано направление, ребро проходится только в одну сторону, и матрица смежности несимметрична; у неориентированного направлений нет, ребро проходится в обе стороны, и матрица смежности симметрична.

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

В матрицу смежности взвешенного графа вместо единиц записывают веса рёбер; нули по-прежнему означают, что ребра между вершинами нет.

Например, если вершины — города, а рёбра — дороги между ними, то весом ребра удобно взять расстояние в километрах.

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

В мультиграфе допускается несколько рёбер между одной и той же парой вершин; такие рёбра называются кратными. В обычном графе двух вершин соединяет не больше одного ребра.

Пример: между двумя городами есть платная и бесплатная дороги, и протяжённость у них разная. Чтобы показать обе, нужны два ребра между одной парой вершин, то есть мультиграф.

Ответ: в мультиграфе, в отличие от обычного графа, одну и ту же пару вершин может соединять несколько рёбер — кратные рёбра.

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

Значит, в простом графе у рёбер нет ни направлений, ни весов, а каждая пара вершин либо соединена ровно одним ребром, либо не соединена вовсе. Именно такие графы рассматриваются чаще всего.

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