Обсуждение:Практическое применение раскраски графов

Построение графа — назовём его графом несовместимостей (англ. interfernce graph, conflict graph). Вершины данного графа — регистры. Вершины смежны, если соответствующие переменные «значимы» одновременно

Судя по всему, тут имеются ввиду виртуальные регистры промежуточного представления. Может, все-таки, вершины данного графа — переменные? JohnCapfull 16:48, 24 октября 2012 (UTC)

Это (почти весь) мой реферат - но, думаю, материал после небольшой доработки вполне в стиле Википедии.

Это - его введение:

В этой работе будут рассмотрены применения задачи раскраски графов на практике. Для каждого применения – отмечена конкретная постановка задачи раскраски графов именно в контексте данного приложения, упомянуты ссылки на литературу и прочие источники информации для более детального исследования вопроса. Иногда, к тому же, освещены основные алгоритмы решения, подходящие именно для этой задачи, - если они достаточно короткие и простые.

Не ставится цели упомянуть обо всех хотя бы даже самых важных применениях этой теоретической модели - но делается попытка привести как можно больше таких примеров. Так же, конкретным реализациям алгоритмов раскраски внимания уделено не было, поскольку это – отдельная широкая тема. И ещё одно ограничение, соблюдённое в работе: области, смежные с раскраской графов, - такие, как нахождение максимального независимого множества вершин, наибольшей клики, - так же не рассматриваются; хотя, отдельным интересным исследованием было бы проследить трансформацию задачи о раскраске графов - посредством, например, ввода дополнительных ограничений - в какую-либо другую - в контексте практического применения.

Сразу укажем библиографию [Culberson04] как хороший источник ссылок на информацию по многим аспектам раскраски графов, в т.ч. её практическому применению. Есть ещё одна большая, хоть и на 2010 год уже очень давно не обновляемая – [Trick94] .

Постановку задачи различиных раскрасок здесь обсуждать почти не будем – посчитаем её известной.

Понятно дело, надо ещё в статье расставить всякие ссылки/интервики.

Проблема тут в - "Постановку задачи различиных раскрасок здесь обсуждать почти не будем" - постановка эта не очень-то хорошо (пока) освещена в русской Википедии.

Leonius 18:36, 12 марта 2010 (UTC)

И ещё, надо как-то сделать гиперссылками сноски на "источники" из основного текста.

Leonius 18:38, 12 марта 2010 (UTC)

• Leonius, вступление, которое хорошо для реферата, не может быть применено в энциклопедической статье. Для начала нужно написать, что же такое "раскраска графа" и где она может применяться, а затем уже приводить различные классификации.
• Оформить сноски на источники можно с помощью подстановки такой конструкции: <ref> Описание источника </ref> после фразы из источника, а перед списком ссылок нужно поставить следующее: == Примечания == {{примечания}} . Более подробно о сносках написано здесь.
• Само описание источника Вы можете сделать с помощью следующих шаблонов: Шаблон:Cite web, Шаблон:Книга и Шаблон:Статья. О ссылках на источники подробно рассказано здесь -- Felitsata 18:21, 14 марта 2010 (UTC)

Да, ещё надо определить саму раскраску графов

Страница хроматическое число, ИМХО, не очень понятно начинает с точки зрения хроматического числа, а не с раскраски графа. Ну это-то ладно.

Но вот стоит определить где-нибудь:

• раскраска графа в общем случае
• n-раскраска (графа)
• T-раскраска (графа)
• списочная T-раскраска (графа) (англ. set T-coloring)
• вершинная раскраска (графа)
• distance-1, distance-2 раскраски (Как это по-русски то?)
• Вынести из статьи, может:
  • звёздная раскраска (графа) (англ. star coloring)
  • ациклицеская раскраска (англ. acyclic coloring)
• Цвет (теория графов)
• параллелизм на уровне команд или параллелизм на уровне инструкций

Leonius 14:01, 22 марта 2011 (UTC)

Энциклопедичность объекта

Может, лучше эту статью в Викиучебник? Там таких не хватает как раз, а здесь это слишком подробно. Ссылку из статьи "хроматическое число" на этот учебнник поставить.

Стиль статьи не соответствует правилам Википедии. Как минимум, необходимо переоформить статью так, чтобы она была от третьего лица, т.е. без авторского "мы". См. ВП:Правила_и_указания#Язык и стиль. --пёс-призраг 11:00, 13 февраля 2012 (UTC)