0
голосов
0
ответов
29 показов
Докажите, что если степень каждой вершины графа не превосходит d
Докажите, что если степень каждой вершины графа не превосходит d, то его можноправильно раскрасить в d + 1 цвет.
0
голосов
0
ответов
17 показов
Пусть G — связный граф, который не является графом-путём
Пусть G — связный граф, который не является графом-путём. Докажите, что в G естьтри вершины v1, v2, v3, в результате удаления которых вместе со всеми ...
0
голосов
1
ответ
143 показа
Найти количество циклов длины 3
В графе на 100 вершинах, каждая из которых имеет степень 3, есть ровно 600 путей длины 3. Сколько в этом графе циклов длины 3?
0
голосов
1
ответ
48 показов
Как сделать несвязным граф?
В связном графе 12 вершин,степень каждой вершины 7.Сколько вершин нужно разрушить,чтобы граф стал несвязным?
1
голос
1
ответ
40 показов
Графы, олимпиадная задачка
В государстве 1000 городов и совсем нет дорог. Король Василий I хочет соединить каждую пару городов дорогой. Для этого он каждый год разбивает города ...
1
голос
1
ответ
108 показов
Задача на подсчёт количества способов в графах
На танцы пришло 10 юношей и 12 девушек. Сколько есть вариантов составить из них пары на вечер так чтобы каждый танцевал с нечётным количеством партнёр ...
0
голосов
0
ответов
42 показа
На любом перекрёстке сходятся ровно три улицы
В некотором городе на любом перекрёстке сходятся ровно три улицы. Улицы раскрашены в три цвета так, что на каждом перекрёстке сходятся улицы трёх разн ...
0
голосов
0
ответов
34 показа
Понимание изоморфизма графов
Есть некоторый граф на n вершинах (Пусть для наглядности n = 5). Все его вершины можно расположить в ряд, граф от этого не меняется. Граф называется и ...
0
голосов
0
ответов
36 показов
Карабасы и барабасы
В сказочной стране Перра—Терра среди прочих обитателей проживают карабасы и барабасы. Каждый карабас знаком с шестью карабасами и девятью барабасами. ...
0
голосов
0
ответов
58 показов
Задача по дискретной математике
Здравствуйте!Задача такая. Нужно доказать, что граф с более чем одной вершиной связен тогда и толькотогда, когда все его вершины лежат на некотором ци ...
1
голос
1
ответ
50 показов
Друзья и враги
В коллективе n сотрудников. Каждые двое из них либо друзья, либо враги, причём у каждого сотрудника ровно 3 врага. Каждый сотрудник может правдиво зая ...
1
голос
1
ответ
88 показов
Жили-были 20 шпионов
Жили-были 20 шпионов. Каждый из них написал донос на 10 своих коллег. Докажите, что не менее чем 10 пар шпионов донесли друг на друга.
0
голосов
0
ответов
70 показов
Изоморфность графов
Перечислите все связные плоские графы (с точностью до изоморфизма), у которых степени всех вершин равны и "степени" всех граней равны (т.е. граница ка ...
1
голос
0
ответов
77 показов
Телефоны в городе Кательниче
В городе Кательниче 10000 телефонов, номера которых задаются четырехзначными числами. В центральном районе установлено более половины всех телефонов и ...
1
голос
1
ответ
121 показ
Задача на графы
Дан связный граф на 2016 вершин. За одну операцию можно выбрать две вершины на максимальном (по количеству ребер) расстоянии и соединить ребром. Может ...
491 вопрос
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.