ТЕОРИЯ ГРАФОВ
Графом называется геометрическая фигура, состоящая из точек и соединяющих их линий. Точки называются вершинами графа, а линии — ребрами. Два ребра называются смежными, если они имеют общую вершину. Два ребра называются кратными, если они соединяют одну и ту же пару вершин. Ребро называется петлей, если его концы совпадают. ОСНОВНЫЕ ТЕРМИНЫ
Ориентированный граф — граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Неориентированный граф - г раф, ни одному ребру которого не присвоено направление Взвешенный граф - граф, в котором у каждого ребра и/или каждой вершины есть “вес” - некоторое число, которое может обозначать длину пути, его стоимость и т. п. Невзвешенный граф - это граф, в котором ребра не имеют весов или связанных с ними затрат. Вместо этого они просто представляют наличие соединения между двумя вершинами.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Вершина называется четной, если ее степень — число четное. Вершина называется нечетной, если ее степень — число нечетное. Две вершины графа называются смежными, если существует соединяющее их ребро Путём в графе называется последовательность вершин, каждая из которых соединена со следующей ребром. Чаще всего под “путём” подразумевают простой путь, все вершины которого различны. Путь, который проходит через какую-либо вершину более одного раза называют сложным путём. Если первая вершина пути совпадает с последней, то такой путь называют циклом.
Матрица смежности - это квадратная матрица, в которой и число строк, и число столбцов равно n - числу вершин графа. В ячейки матрицы смежности записываются некоторые числа в зависимости от того, соединены соответствующие вершины рёбрами или нет, и от типа графа.
Задача 1
3 3 3 3 4 4 2 3 3 3 3 4 4 2 К Д Е В Задача 1
Задача 2 Ответ: 20
Задача 3 Ответ: 9
Задача 4 Ответ: 26
Задача 5 Ответ: 6
Задача 6 Ответ: БЖКИДАЕГВ
Задача 7 Ответ: 35
Задача 8 Ответ: 13
Задача 9 Ответ:15
Задача 10 Ответ: 18
Задача 11 Ответ: 7
Задача 12 Ответ: 6 дорог
