Обсуждение:Теория графов

Untitled

IMHO стоит заменить ссылку на Зыкова:

А. А. Зыков, Основы теории графов, М.: Вузовская книга, 2004.

в этом издании добавлено много материала, в том числе и исторического характера.

tim2 02:11, 16 октября 2007 (UTC)

• Заменено. Matsievsky (обс.) 12:47, 5 августа 2023 (UTC)

Пора снять шаблон

Пора снять шаблон "к объединению", т.к. объединять уже не с чем - вторая статья удалена.--tim2 11:05, 6 января 2009 (UTC)

Про терминологию

С терминологией действительно есть проблемы, кстати, прошу высказаться на Обсуждение:Словарь_терминов_теории_графов. Но вот то что в этом подразделе написано сейчас, не удовлетворительно. Написано, что нечто надо называть то-ли графом то ли сетью. Неоднозначность имхо связана только с термином сеть. Это то ли граф, в котором множество ребер инцидентных вершине образует упорядоченный список, (а не множество как в обычном графе) то ли определенным образом помеченный граф, частный случай - сеть Петри. А вот в определении Харари метятся только ребра и только положительными числами. А тут в словаре сейчас написано, что сеть и граф это одно и то же. Leshabirukov 11:42, 14 февраля 2009 (UTC)

"только с термином сеть" - а с термином "вершина/узел" - всё 1значно? В чём отличие от понятия "точка (геометрия)"? Fractaler 20:02, 14 февраля 2009 (UTC)

Ну, например у точки (на плоскости с метрикой) есть координаты, а у не помеченной вершины есть только множество инцидентных ребер. А укладка графа на поверхности действительно геометрический объект, там мы имеем дело с образами вершин и ребер - точками и линиями соответственно.Leshabirukov 23:12, 14 февраля 2009 (UTC)

Зачем же ограничения? Без метрики (для графа она не вводится же). Сравнивается 1 вершина/узел и 1 точка. И, например, пустой граф (Нуль-граф), т.е., граф, не содержащий рёбер - множество Точек (без линий). Fractaler 14:55, 16 февраля 2009 (UTC)

Особых проблем нет: очень часто можно встретить названия книг, как, например, М.И.Нечепуренко и др. Алгоритмы и программы решения задач на графах и сетях, Н:Наука, 1990, 515 С. Где особых различий между терминами граф и сеть не приводится. Традиционно в некоторых приложениях графы называют сетью, например, Интернет мы называем сетью, что не мешает рассматривать его как граф. Граф - конечно же чистая топология, можем, когда нужно для задачи, задать длины ребер, но никаких углов между ребрами никогда не рассматривается, в этом отличие графа от его изображения. В некоторых случаях авторы делают оговорку, что, например, они будут в дальнейшем говорить только об ориентированных графах и для краткости будут называть их просто графами и т.д. По определению граф - это пара множеств: вершин и ребер, а как в частном случае их сортируют, какие веса и индексы приписывают - это все частности. Короче говоря - не стоит изобретать терминологическую проблему!--tim2 16:34, 16 февраля 2009 (UTC)

Предположим, надо описать электрическую схему. Естественное решение - элементы представляем узлами сети, а электрические соединения ребрами. Как вы обозначите что вот эта нога транзистора скажем, эмиттер? Если сеть это просто помеченный граф, то инцидентные вершине ребра неупорядочены. Метить ребра нехорошо, у них другой смысл и к одной ноге может идти несколько ребер-соединений. Представить транзистор подграфом можно, но это неестественное решение. А надо всего-то разрешить упорядочивать инцидентные вершине ребра. Но это уже не граф.Leshabirukov 18:45, 19 февраля 2009 (UTC)

Линия это непрерывный объект и состоит из точек. Нельзя сказать, что ребро состоит из вершин.Leshabirukov 18:45, 19 февраля 2009 (UTC)

Речь идёт пока только о термине «точка» и «вершина/узел». А если говорить ещё и о ребрах, то множество рёбер является подмножеством «вершина/узел/точка». То, что у нас получается комбинаторикой элементов базового множества (рёбра - вершинами, линии - упорядоченными точками) - это дело следующее. Fractaler 14:18, 20 февраля 2009 (UTC)

• "Естественное решение - элементы представляем узлами сети, а электрические соединения ребрами. Как вы обозначите что вот эта нога транзистора скажем, эмиттер?" - Очевидно, что точки соединения ноги-эмиттера и ноги-базы могут находиться под разным потенциалом, а значит, отождествлять их с одной и той же вершиной может быть неверно с точки зрения физики схемы. Геометрически эти точки также не совпадают, т.о. с точки зрения топологии схемы отождествлять их с одной и той же вершиной также может быть не целесообразно - для трассировки печатной платы, например, на этапе, где нам нужно получить минимум пересечений проводников, при этом точные расстояния между ногами мы можем не учитывать. Можно представить транзистор одной вершиной, можно тремя - это Ваш выбор, а теория графов от предметных областей не зависит... --tim2 19:15, 20 февраля 2009 (UTC)

• "А надо всего-то разрешить упорядочивать инцидентные вершине ребра. Но это уже не граф." - Никто Вам этого не запретит, если, например, для Вашей модели е-схемы это нужно. Так в прикладных задачах нередко и поступают. И не только в прикладных: очевидно, чтобы эффективно работать с графами, нужно их наглядное представление, выше мы говорили, что граф - чистая топология, и понятие угла между ребрами не имеет смысла, но! в алгоритмах визуализации графов (неприкладная задача) для изображения вычисляют те самые углы...--tim2 19:15, 20 февраля 2009 (UTC)

• "Линия это непрерывный объект и состоит из точек. Нельзя сказать, что ребро состоит из вершин." - конечно, нельзя, точка и линия - это вообще не термины теории графов.--tim2 19:15, 20 февраля 2009 (UTC)

• "Метить ребра нехорошо" - Почему нехорошо? Во многих фундаментальных алгоритмах ребра метят, как и вершины. А нумерация ребер разве не их разметка?--tim2 19:15, 20 февраля 2009 (UTC)

• Fractaler-у: остаюсь при своем мнении, путать геометрию с теорией графов нельзя. Укладка графа есть не граф, а его изображение, максимум - модель. Даже термин "плоский граф" нужно очень осторожно применять.

• Tim2-у: ..."Метить ребра нехорошо" - Почему нехорошо?... Потому, что вид ноги транзистора это внутреннее свойство самого транзистора, а ребро это модель соединения, проводника. ...отождествлять их с одной и той же вершиной может быть неверно... узел сети это уже не точечный объект, вспомните, как рисуется транзистор на схеме. На изображении есть несколько различаемых входов, соответственно в сети (в той её интерпретации, что я сейчас защищаю) инцидентные ребра упорядочены в соответствии с сортом входа.

"вид ноги транзистора это внутреннее свойство самого транзистора" - не понял - внутрь транзистора я лезть не предлагаю, но в соответствии с концепцией черного ящика, я имею право знать его внешние характеристики - т.е. какой эффект я получу от того или иного воздействия. Для характеристик транзистора принципиально различать его выводы (внешние - внутри транзистор может быть и составным). Как рисуется транзистор - это дело десятое - дело ГОСТа. "в сети (в той её интерпретации, что я сейчас защищаю" - опять не понял - зачем Вы здесь защищаете эту интерпретацию? У данной страницы иная тема, теория графов и ее основные термины не изменятся от того, сможете ли Вы или не сможете предложить новую модель для электронных схем.--tim2 17:36, 25 февраля 2009 (UTC)

Всё-таки этот раздел надо переписать или удалить. При всём уважении к программистам, то, что “в программистском мире нет единого мнения о том, какой из двух терминов "граф" или "сеть"” (кстати, предложение незаконченно), ничего не говорит о разработанности области математики, называемой теорией графов. В математике есть понятие графа, сеть может быть частным случаем, но вряд ли синонимом; у графа есть вершины, у дерева --- узлы, про точки ни разу не слышал (я математик, но не специалист в теории графов). С. Н. Фёдоров 17:42, 18 июня 2014 (UTC)

Стиль статьи

1) На мой взгляд нужно сокращать дублирование данных в разделах доказательств теорий и гипотез (переписывать здесь не формальными доказательствами, а простыми объяснениями)
2) "Легендарные издания" - две книги?
3) Краткая хронология" - вообще не формат (но основа для структуры статьи)
4) Современное состояние теории графов - это перечисление терминов, с учётом что есть статья Глоссарий теории графов. Saramag (обс.) 16:01, 30 июня 2021 (UTC)

• Saramag, спасибо за замечания.
  

1) Очень стараюсь писать простыми словами и использовать минимум терминов, в теории графов любят вводить дополнительные обозначения для сокращения (?) письма. Доказательства использую крайне редко, только очень короткие и элементарные для демонстрации движения мысли. Особого дублирования пока не замечал, основные статьи если и существуют, то написаны не очень хорошо. И уж точно без многочисленных иллюстраций, иногда приходится заливать файлы для иллюстраций.
2) Заменил на "Основные легендарные издания". Это очень краткая история теории графов, для нормальной истории нужно писать отдельную статью, которой пока нет и проблема с источниками.
3) Нет, "Краткая хронология" - не основа для структуры всей статьи, а основа для структуры "Истории возникновения теории графов". И что значит "не формат"?
4) "Современное состояние теории графов" - это не просто перечисление терминов, это очень краткий обзор теории графов по современной монографии Дистеля. Планируется 11 параграфов, залито 5, остальные в работе. Не перечисляются, а разъясняются основные термины 11 разделов с максимальным разумным количеством иллюстраций. Приводятся основные простейшие теоремы, написанные по возможности простым языком без значков. Глоссарий теории графов - это совсем другое, просто перечисление, и есть далеко не все, что используется в кратком обзоре. Будет переписана также глава "Терминология теории графов", где, в частности, будут проиллюстрированы основные термины, которые затем используются в 11 параграфах следующей главы. — Matsievsky (обс.) 16:34, 30 июня 2021 (UTC)

• Про замечание об отсутствии ссылки. Сказалась ущербность английского формата текста статей РуВики - отсутствие красной строки. В начале главы был один абзац, а не два, но визуально этого не видно. Однако продублировал ссылку. — Matsievsky (обс.) 16:59, 30 июня 2021 (UTC)
  • "не формат" - в дублировании данных. Обычно есть преамбула, в которой идёт перечисление основных вех, потом оглавление (в которое я и предлагаю переделать хронологию), затем раскрытие темы. А тут получается где-то в середине статьи хронология краткая. Saramag (обс.) 18:09, 30 июня 2021 (UTC)
    • Saramag, перенес таблицу с хронологией в начало главы. — Matsievsky (обс.) 21:49, 30 июня 2021 (UTC)
      • Да, спасибо. Я попробую если время появится подрихтовать оформление. Saramag (обс.) 13:55, 1 июля 2021 (UTC)