Обсуждение:Максимальное независимое множество

Наибольший и максимальный

Традиционно в теории графов максимальным называется множество (граф), не являющееся собственным подмножеством (подграфом) другого множества (графа) с теми же свойствами, а наибольшим — множество (граф), имеющее наибольшую возможную мощность (порядок) среди всех множеств (графов) с теми же свойствами. Это относится и к независимому множеству, и к паросочетанию, и к клике, и ко всему остальному. См.

• Зыков А. А. Основы теории графов. — М.: Наука, 1987, 384 с.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. — М.: Наука, 1990, 384 с.
• Фляйшнер Г. Эйлеровы графы и смежные вопросы. Пер. с англ. — М.: Мир, 2002, 176 с.

и другие русскоязычные источники. Не стоит вносить путаницу из-за встречающегося неграмотного перевода англоязычных статей. 178.124.207.221 08:37, 20 июня 2014 (UTC) Магистр физ.-мат. наук, аспирант-исследователь в области теории графов.

• Спасибо за существенно замечание. Необходимо будет проверить все вхождения "максимальное независимое" и "наибольшее независимое"... Предлагаю сделать это вам - я смогу это сделать лишь недели через две-три. Jumpow 09:45, 20 июня 2014 (UTC)Jumpow
  • Однажды я уже редактировал статью про алгоритм для поиска наибольшего паросочетания, когда там были правильные определения, но далее термины использовались не по назначению (вместо наибольшего писали про максимальное). Не знаю, сколько продержались мои правки, но сейчас я вижу, что переиначили все сходные теоретико-графовые определения…
  • Беда в том, что есть опубликованный источник (региональный), в котором термины перепутаны. Тем не менее, Александр Александрович Зыков стоял у истоков теории графов на территории Советского Союза, а Емеличев, Мельников, Сарванов и Тышкевич — его ученики и основатели школы теории графов в БССР. Поэтому этих авторов я считаю более авторитетными. При необходимости могу в подтверждение своих слов поискать другие источники, коих должно быть великое множество. Остаётся вопрос, как избежать войны правок.178.124.204.75 17:54, 27 июня 2014 (UTC) Магистр физ.-мат. наук, аспирант-исследователь в области теории графов.
    • Я думаю, вы правы. Но теперь нужно просматривать все аналогичные статьи.
    • Так, например, та же беда в статье "Паросочетание", а в статье "Глоссарий теории графов" определения противоречивы

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

      множество S*, на котором этот максимум достигается, называется наибольшим независимым множеством.

    • Нужно бы всё привести к одному виду. Во избежание войны правок следует вынести этот вопрос на обсуждение общественности. Пока я занят другими делами, и в ближайшее время это сделать не смогу. Попробуйте вы.
    • А правки в начале августа я бы сделал, если к этому времени народ придёт к единому мнению.Jumpow 17:13, 8 июля 2014 (UTC)Jumpow
      • Я не так хорошо знаком с тем, как на Википедии организован процесс выявления, кто прав и кто виноват, и разрешение конфликтов. Я могу только привлечь внимание более опытного участника к существующей проблеме и дать большое число ссылок на авторитетные источники.178.124.106.70 16:48, 5 августа 2014 (UTC) Магистр физ.-мат. наук, аспирант-исследователь в области теории графов.
• Jumpow, ну как, чем закончилось всё? Сейчас по сравнению с тем, что предлагает аноним, всё наоборот, так и должно быть? Вопрос возник в связи с тем, какие метки ставить в максимальное независимое множество (Q7888149) и наибольшее независимое множество (Q93597459). Викизавр (обс.) 13:38, 8 мая 2020 (UTC)
  • Закончилось пожеланием привести к единому виду... Нужно везде изменить так, что максимальный предполагает упорядочение по включению, а наибольший означает упорядочение по мощности. Если есть желание и время, меняйте смело. Jumpow (обс.) 18:21, 8 мая 2020 (UTC)
    • Угу, сделал. Викизавр (обс.) 15:14, 9 мая 2020 (UTC)

Независимое множество

Куда перенаправление должно вести, сюда или на Задача о независимом множестве? Или, может быть, нужно создать отдельную статью? Викизавр (обс.) 13:59, 8 мая 2020 (UTC)

Гм... Интересный вопрос. Думаю, на задачу о независимом множестве. Jumpow (обс.) 18:25, 8 мая 2020 (UTC)