Что такое матрица смежности?

Матрица смежности — это вид представления графа в виде матрицы, когда пересечение столбцов и строк задаёт дуги. Используя матрицу смежности, можно задать вес дуг и ориентацию. Каждая строка и столбец матрицы соответствуют вершинам, номер строки соответствует вершине, из которой выходит дуга, а номер столбца — в какую входит дуга.

Алгоритмы на графах. Алгоритмы обхода графа

Примеры матриц смежности

Граф из 3 соединённых вершин	Граф с ориентированной дугой	Граф из 4 вершин без дуг
0, 1, 1, 1, 0, 1, 1, 1, 0,	0, 1, 0, 0,	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
Ссылка на граф	Ссылка на граф	Ссылка на граф

Использование Матрицы смежности в сервисе Граф Онлайн

Видео справка

Сервис Граф Онлайн предоставляет вам возможность создать Создать граф по матрице смежности.

Также вы можете редактировать существующую матрицу смежности. Для этого вам необходимо выбрать меню Граф -> Матрица смежности.

Для того чтобы использовать матрицу смежности вам необходимо ввести её в правильном формате.

Формат ввода матрицы смежности

Вводя матрицу смежности вам необходимо руководствоваться следующими правилами:

1. Матрица должна быть квадратная — число строк равно числу столбцов.
2. Каждая новая строка вводится с новой строки.
3. Каждое значение разделяется замятой (,)
4. Вес дуг должен быть положительным числом. Значение 0 значит что дуги не существует.

А теперь рассмотрим основные ошибки ввода матриц смежности

Основные ошибки ввода матриц смежности

Примеры решений задач по теории графов

На этой странице вы найдете готовые примеры по теории графов (разделу дискретной математики). Теория графов берет свое начало еще в 18 веке, когда Эйлер написал свою знаменитую статью о Кёнигсберских мостах (см. решения на алгоритм Эйлера). Сейчас достижения теории графов применяются в строительстве, программировании, электротехнике, социологии, экономике, биохимии, телекоммуникациях и планировании транспортных коммуникаций, психологии и т.д.

Какие виды заданий решаются студентами?

Задачи, решаемые в рамках теории графов, можно условно поделить на несколько групп:

• Определение графа и его свойства. Задачи на построение графа по заданному числу вершин и ребер, построение матрицы смежности и инцидентности, вычисление основных характеристик графа (связность, простота, эйлеровость, полнота, двудольность, регулярность графа и т.п.). Проверка планарности и изоморфности графов.
• Действия с графами. Добавление и удаление вершин и ребер, компонент связности, слияние вершин, объединение, пересечение, соединение и декартово произведение графов. Построение дополнение графа.
• Маршруты, цепи и циклы, контуры. Эйлерова цепь и гамильтонов цикл и проверка графа на выполнение этих свойств.

  10 алгоритмов на графах в гифках

• Вычисление характеристик графа. Расстояния: диаметр графа, центр графа, радиус графа. Вычисление цикломатического и хроматического числа.
• Задачи на графах. Задача о кратчайшем пути (алгоритм Дейкстры, Беллмана, построение дерева путей). Задача на построение минимального остовного дерева (алгоритм Краскала). Задача о максимальном потоке в сети (алгоритм Форда-Фолкерсона). Задача о раскраске графа.
• Изучение деревьев (специальных видов графов без циклов). Деревья применяются в шифровании, программировании и многих других прикладных областях.

Задачи по графам с решением онлайн

Задача 1. Постройте граф отношения «x+y ≤7» на множестве М={1,2,3,4,5,6}. Определите его свойства.

Построение графа отношения (pdf, 134 Кб)

Задача 2. Найти кратчайшие пути в орграфе от первой вершины ко всем остальным, используя алгоритм Дейкстры. Постройте дерево кратчайших путей.

Решение по алгоритму Дейкстры (pdf, 196 Кб)

Задача 3. Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок) Построить граф приращений. Проверить выполнение условия максимальности построенного полного потока. Источник – вершина 1, сток – вершина 8.

Решение задачи о нахождении максимального потока в сети (pdf, 282 Кб)

Задача 4. Постройте остовное дерево минимального веса, используя алгоритмы Прима и Краскала. С помощью матрицы Кирхгоффа найдите количество (неизоморфных) остовных деревьев, используя пакеты компьютерной математики (например, MathCAD, Mathematica, MatLab).

Решение задачи на построение остовного дерева (pdf, 173 Кб)

Задача 5. Требуется составить структурную матрицу для данного орграфа (или графа) и, методами булевой алгебры, найти все пути $P_{ij}$ из вершины $i$ в вершину $j$, затем найти все сечения $S_{ij}$ между этими вершинами. В данном задании (чтобы исключить возможные неясности графического рисунка) указываются все ориентированные ребра, причем запись (2–4) означает, что 2 вершина связана с 4-й, а обратной связи нет. Напомним, что для нахождения путей из вершины $i$ в вершину $j$ нужно раскрывать минор структурной матрицы$М_{ji}$ (вычеркивать из структурной матрицы строчку с номером $j$ и столбец с номером $i$). Сечения же находятся отрицанием путей (конъюнкция меняется на дизъюнкцию и наоборот).

Решение задачи на составление структурной матрицы и сечений

Задача 6. Для графа $G=(X,U)$ выполнить следующее:
1.1. Построить:
— матрицу смежности,
— матрицу инцидентности.
1.2. Определить степени для всех вершин ${x_i}$ данного графа.

Построение матриц смежности и инцидентности

Задача 7. Найти все кратчайшие пути в орграфе, используя алгоритм Флойда.

Поиск кратчайших путей по алгоритму Флойда

Задача 8. Задан $G (X,ГX)$
$X={x1,x2,x3,x4,x5}$,
ГХ:
Гx1={x4}, Гx2={x1,x4}, Гx3={x4,x5}, Гx4={x1,x5}, Гx5={x1,x3}.
Определить хроматическое и цикломатическое число данного графа.

Решение задачи на нахождение чисел графа

Задача 9. Считая данный граф неориентированным, обозначить его вершины и рёбра разными символами и определить.
3.1. Локальные степени и окружения каждой вершины в виде структуры смежности;
3.2. Построить матрицы инцидентности и смежности;
3.3. Рассмотреть части графа. Привести примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры пересечения и объединения частей графа;
3.4. Привести примеры циклического маршрута, цепи, простой цепи. Попытаться найти Эйлеров цикл;
3.5. Определить центр, диаметр и радиус графа.
Считая граф ориентированным, определить
3.6. Степени вершин
3.7. Матрицы инцидентности и смежности.
3.8. Привести примеры пути, ориентированной цепи, простой цепи, контура, цикла и простого цикла.

Решение задачи на исследование графа

Решение теории графов на заказ

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

Стоимость примера от 100 рублей, оформление производится в Word, срок от 2 дней. Также оказываем помощь в сдаче тестов по графам.

Назад: Дискретная математика