Здравствуйте, возник вопрос по решению данной задачи: "перечислить связные графы с n вершинами, (n-2)-я степень матрицы смежности которых имеет неположительные элементы." Помогите, пожалуйста.

задан 12 Фев 23:12

Условие немного странное. Элементы матрицы смежности неотрицательны. При возведении в степень свойство сохраняется. Поэтому можно сказать, что матрица A^{n-2} имеет нулевые элементы. Поскольку степень матрицы содержит информацию о числе путей в графе, можно сказать, что найдутся две вершины i, j (возможно, i=j) такие, что из i в j нет путей длины n-2.

Непонятно, какого ответа здесь хотят: графы с этим свойством не являются какими-то "редкими". Скажем, при n=3 подходит всё кроме треугольника. При n=4 не подходит полный граф, а также полный граф без одного ребра. Общий ответ как-то теряется.

(13 Фев 2:27) falcao

@falcao, спасибо. Согласен, что условие странное, постараюсь уточнить у составителей большее количество деталей.

(13 Фев 2:32) Candell

@Candell: могли иметь в виду следующее. В связном графе на n вершинах всегда есть путь длиной <=n-1 из заданной вершины в заданную. Если граф линейный, то между двумя крайними вершинами нет пути длиной <=n-2. И это единственный такой случай. Поэтому, если заменить (n-2)-ю степень на сумму E+A+A^2+...+A^{n-2}, то получается простое описание.

(13 Фев 12:50) falcao

@falcao, похоже на правду, спасибо большое, если что-то прояснится, то я сообщу

(13 Фев 15:22) Candell
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×544

задан
12 Фев 23:12

показан
113 раз

обновлен
13 Фев 15:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru