Графы: вершины, рёбра и степень вершины
Читай граф: находи степень каждой вершины, сравнивай сумму степеней с числом рёбер и узнай, почему некоторых графов не существует.
- Россия: 10 класс
- Франция: 12 класс
- Иран: 12 класс
Подсказки для взрослых
Граф — это несколько точек и несколько линий (или кривых), которые соединяют некоторые пары этих точек. Каждая точка — вершина, каждая линия — ребро. Графы описывают то, что связано между собой: людей и дружбу между ними, города и дороги.
Степень вершины — это число рёбер, выходящих из неё. Вершина с нечётной степенью называется нечётной, с чётной — чётной. Число вершин — порядок графа, число рёбер — его размер.
В российской программе эта тема изучается в 7 классе (курс «Вероятность и статистика», раздел «Введение в теорию графов»: граф, вершина, ребро, степень вершины, число рёбер и сумма степеней вершин, связность, цепи и циклы). Здесь все графы простые: между двумя вершинами не больше одного ребра, а ребра от вершины к ней самой нет. Вершины обозначены буквами. Нажимай на вершины, чтобы выбрать их, и ещё раз, чтобы снять выбор.