0
голосов
0
ответов
67 показов
Линейный алгоритм нахождения кратчайших путей
Построить линейный по сложности алгоритм нахождения кратчайших путей в ациклическом графе.
0
голосов
0
ответов
38 показов
Теория графов. Хроматическое число/индекс
В каких границах может быть хроматическое число связного графа на 6 вершинах? Тот же вопрос про хроматический индекс. Для каждого граничного значения ...
1
голос
1
ответ
63 показа
Задача про ориентированный граф.
Докажите, что на n (n>4) вершинах можно построить ориентированный граф, в котором для любых двух вершины существует ориентированный путь из одной в ...
0
голосов
1
ответ
49 показов
Радиус, диаметр и связность графа подстановок степени n
Графом подстановок степени n называется граф на n! вершинах, соответствующих подстановкам из Sn, в котором вершины смежны тогда и только тогда, когда ...
0
голосов
0
ответов
44 показа
Минимальный многочлен матрицы смежности графа
Как наиболее оптимально найти степень минимального многочлена матрицы смежности обыкновенного орграфа?
0
голосов
0
ответов
48 показов
Связь матриц инцидентности изоморфных графов
Доказать, что графы G и H изоморфны тогда и только тогда, когда матрица инцидентности графа G получается из матрицы инцидентности графа Н перестановко ...
0
голосов
1
ответ
70 показов
Группа автоморфизмов графа
Доказать, что AutG={s€Sn: MsA(G)=A(G)Ms}, где Ms - подстановочная матрица, соответствующая постановке s, а A(G) - матрица смежности графа G.
0
голосов
1
ответ
54 показа
Задача на графы.
Но шахматной доске 8х8 расставили ладей так, что в каждом столбце и в каждой строке ровно 3 ладьи. Докажите, что можно выбрать 8 ладей так, что никаки ...
0
голосов
0
ответов
72 показа
Теория графов. Перечисление неизоморфных графов
Перечислите все попарно неизоморфные связные простые графы на шести вершинах, в которых ровно три блока. Подробно описывать перебор не нужно, но обяза ...
0
голосов
0
ответов
89 показов
Орграф и циклы без хорд
Добрый день! Вот такая задача встретиласьПокажите, что орграф, который можетбыть дополнен до турнира менее чем $%k $% ребрами ($% k \geq 2$%), не може ...
0
голосов
0
ответов
90 показов
Задача с весами
На чашечных весах с обеих сторон лежит по 80 гирь, причем на каждой из чаш не все гири имеют одинаковую массу. Весы находятся в равновесии. За ход мы ...
0
голосов
0
ответов
33 показа
Произвольно вычерчиваемый граф
Граф называется произвольно вычерчиваемым из вершины v, если следующая процедура всегда приводит к эйлеровой цепи: начиная с произвольной вершины v, и ...
0
голосов
1
ответ
61 показ
Задача про граф.
Дан граф на n вершинах. Оказалось, что степень каждой вершины не превосходит 2k и каждые две не смежные вершины имеют не менее k вершин смежных им обе ...
0
голосов
0
ответов
60 показов
Теория графов. Построение унициклического графа
Существует ли унициклический граф, последовательность степеней вершин которого будет равна (1,1,1,1,1,1,2,2,3,3,4)? Если да, то постройте такой граф.
-1
голосов
0
ответов
65 показов
Теория графов
Дана таблица 100 х 2 (где 100 строк и 2 столбца), которая заполнена числами 0, 1, ..., 9 и выполнены следующие условия: 1) все строки различны; 2) нел ...
233 вопроса
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.