2004-gre-cs-practice-book.pdf/Q43 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия этого же участника)
Строка 1: Строка 1:
−
{{reserve-task|[[Участник:Urmat A|Urmat A]] 14:54, 21 декабря 2024 (UTC)}}
 
 
== Вопрос: Q43-4c9f66 ==
 
== Вопрос: Q43-4c9f66 ==
  
Строка 6: Строка 5:
 
Пусть ''M'' и ''m'', соответственно, являются максимальным и минимальным количеством [https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D0%B0_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 связанных компонентов] в любом графе в коллекции.
 
Пусть ''M'' и ''m'', соответственно, являются максимальным и минимальным количеством [https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D0%B0_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 связанных компонентов] в любом графе в коллекции.
  
−
Если граф не имеет <s>замкнутых циклов</s> [https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%82%D0%BB%D1%8F_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)#:~:text=%D0%9F%D0%B5%CC%81%D1%82%D0%BB%D1%8F%CC%81%20%D0%B2%20%D0%B3%D1%80%D0%B0%D1%84%D0%B5%20%E2%80%94%20%D1%80%D0%B5%D0%B1%D1%80%D0%BE%2C%20%D0%B8%D0%BD%D1%86%D0%B8%D0%B4%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B5%20%D0%BE%D0%B4%D0%BD%D0%BE%D0%B9%20%D0%B8%20%D1%82%D0%BE%D0%B9%20%D0%B6%D0%B5%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%B5.&text=%D0%92%20%D0%BD%D0%B5%D0%BA%D0%BE%D1%82%D0%BE%D1%80%D1%8B%D1%85%20%D1%83%D1%87%D0%B5%D0%B1%D0%BD%D0%B8%D0%BA%D0%B0%D1%85%20%D0%B3%D1%80%D0%B0%D1%84%20%D0%BF%D0%BE,%D0%B1%D0%B5%D0%B7%20%D0%BF%D0%B5%D1%82%D0%B5%D0%BB%D1%8C%20%E2%80%94%20%D1%8D%D1%82%D0%BE%20%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B9%20%D0%B3%D1%80%D0%B0%D1%84. петель] и между любой парой узлов имеется не более одного ребра, что из следующего '''верно'''?
+
Если граф не имеет [https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%82%D0%BB%D1%8F_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)#:~:text=%D0%9F%D0%B5%CC%81%D1%82%D0%BB%D1%8F%CC%81%20%D0%B2%20%D0%B3%D1%80%D0%B0%D1%84%D0%B5%20%E2%80%94%20%D1%80%D0%B5%D0%B1%D1%80%D0%BE%2C%20%D0%B8%D0%BD%D1%86%D0%B8%D0%B4%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B5%20%D0%BE%D0%B4%D0%BD%D0%BE%D0%B9%20%D0%B8%20%D1%82%D0%BE%D0%B9%20%D0%B6%D0%B5%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%B5.&text=%D0%92%20%D0%BD%D0%B5%D0%BA%D0%BE%D1%82%D0%BE%D1%80%D1%8B%D1%85%20%D1%83%D1%87%D0%B5%D0%B1%D0%BD%D0%B8%D0%BA%D0%B0%D1%85%20%D0%B3%D1%80%D0%B0%D1%84%20%D0%BF%D0%BE,%D0%B1%D0%B5%D0%B7%20%D0%BF%D0%B5%D1%82%D0%B5%D0%BB%D1%8C%20%E2%80%94%20%D1%8D%D1%82%D0%BE%20%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B9%20%D0%B3%D1%80%D0%B0%D1%84. петель] и между любой парой узлов имеется не более одного ребра, что из следующего '''верно'''?
  
 
=== Ответы ===
 
=== Ответы ===
Строка 18: Строка 17:
 
{{cstest-source|2004-gre-cs-practice-book.pdf|31|43}}
 
{{cstest-source|2004-gre-cs-practice-book.pdf|31|43}}
  
−
В оригинале — Правильный ответ «M = 7, m = 4».  
+
 
−
Но это же бред.
+
Для максимизации компонент — максимально пакуем ребра в полный граф, и одиночки отдельно.
−
* Без циклов — компоненты будут остовными деревьями, «число ребер на единицу меньше числа вершин».
+
 
−
* Т.е. число связных компонент определяется однозначно — число вершин минус число ребер, чтобы не делать.
+
<neato>
−
* Ну или я ошибаюсь?
+
graph G{
 +
1 2 3 4 5 6 7 8 9 10
 +
1--2--3--4
 +
1--3
 +
1--4
 +
2--4
 +
}
 +
</neato>
 +
 +
 
 +
Для минимизации компонент — используем максимум «потенциала ребра», не допускаем циклов, делаем только любые варианты остовных деревьев, результат будет один и тот же
  
 
<neato>
 
<neato>
Строка 53: Строка 62:
 
</neato>
 
</neato>
  
−
-------------------------
 
−
Я уже указал, что перевод был не верный. В оригинале говорится о self-loops, то есть о [https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%82%D0%BB%D1%8F_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)#:~:text=%D0%9F%D0%B5%CC%81%D1%82%D0%BB%D1%8F%CC%81%20%D0%B2%20%D0%B3%D1%80%D0%B0%D1%84%D0%B5%20%E2%80%94%20%D1%80%D0%B5%D0%B1%D1%80%D0%BE%2C%20%D0%B8%D0%BD%D1%86%D0%B8%D0%B4%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B5%20%D0%BE%D0%B4%D0%BD%D0%BE%D0%B9%20%D0%B8%20%D1%82%D0%BE%D0%B9%20%D0%B6%D0%B5%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%B5.&text=%D0%92%20%D0%BD%D0%B5%D0%BA%D0%BE%D1%82%D0%BE%D1%80%D1%8B%D1%85%20%D1%83%D1%87%D0%B5%D0%B1%D0%BD%D0%B8%D0%BA%D0%B0%D1%85%20%D0%B3%D1%80%D0%B0%D1%84%20%D0%BF%D0%BE,%D0%B1%D0%B5%D0%B7%20%D0%BF%D0%B5%D1%82%D0%B5%D0%BB%D1%8C%20%E2%80%94%20%D1%8D%D1%82%D0%BE%20%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B9%20%D0%B3%D1%80%D0%B0%D1%84. петлях]. Поэтому циклы допускаются и легко привести пример такого графа с 7 компонентами связности.
 
−
 
−
<neato>
 
−
graph G{
 
−
1 2 3 4 5 6 7 8 9 10
 
−
1--2--3--4
 
−
1--3
 
−
1--4
 
−
2--4
 
−
}
 
−
</neato>
 
−
 
−
Думаю очевидно, что если взять больше 4 вершин и соединить их 6 рёбрами, то больше компонент связности не получится. Как и если взять по 3 вершины, будет тоже самое.
 
  
 
{{question-ok|[[Участник:StasFomin|StasFomin]] 14:18, 15 декабря 2024 (UTC)}}
 
{{question-ok|[[Участник:StasFomin|StasFomin]] 14:18, 15 декабря 2024 (UTC)}}
−
{{checkme|[[Участник:Urmat A|Urmat A]] 15:12, 21 декабря 2024 (UTC)}}
 
  
 
[[Категория:Алгоритмы на графах]]
 
[[Категория:Алгоритмы на графах]]
−
[[Категория:Разобраться]]
 

Текущая версия на 19:27, 23 декабря 2024

Вопрос: Q43-4c9f66

Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами.

Пусть M и m, соответственно, являются максимальным и минимальным количеством связанных компонентов в любом графе в коллекции.

Если граф не имеет петель и между любой парой узлов имеется не более одного ребра, что из следующего верно?

Ответы

  • M = 10, m = 10
  • M = 10, m = 1
  • Правильный ответ: M = 7, m = 4
  • M = 6, m = 4
  • M = 6, m = 3

Объяснение

Исходники — вопрос 43 на 31 странице книги «2004-gre-cs-practice-book.pdf»


Для максимизации компонент — максимально пакуем ребра в полный граф, и одиночки отдельно.

[svg]


Для минимизации компонент — используем максимум «потенциала ребра», не допускаем циклов, делаем только любые варианты остовных деревьев, результат будет один и тот же

[svg]

[svg]

[svg]

Источник — «https://discopal.ispras.ru/index.php?title=2004-gre-cs-practice-book.pdf/Q43&oldid=34727»