Task 107. Основы графов

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

Входные данные: arr - матрица размерности NxN, состоящая из нулей и единиц. N от 1 до 1000.

Вывод: True - если матрица arr является матрицей смежности простого неориентированного графа. False - в противном случае.

Пример:

arr = [[0 1], [1 0]]

Answer = True

графы бывают и такие :)

Идея: нужно просто вспомнить теорию графов, а именно определение матрицы смежности и простого неориентированного графа.

Подробнее про графы вы можете посмотреть тут:

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

Т.е. в нашей задаче по условию нам уже дана квадратная матрица с нулями и единицами, поэтому необходимо проверить только на симметричность относительно главной диагонали. Но также нужно проверить нет ли петли для элементов, ктр находятся на главной диагонали, т.е. если элемент матрицы arr[i, i] = 1, то в вершине i есть петля.

Реализация:

Test:

Task 107. Основы графов

Report Page