Комментарии 15
Фамильное дерево не является деревом. Из-за инбридинга там появляются слияния, и хоть оно остаётся DAG, деревом оно быть перестаёт.
А примеры надо всё-таки серьёзные, а не на 10 элементов. Проблема графов в том, что они либо тривиально решаются руками (и шапкозакидательными алгоритмами - даже n! для современных компьютеров не проблема при n=10), либо их не нарисовать "наглядно".
А примеры трушных графов надо. Например, кусок карты из OSM'а. А ещё? Например, покажите мне разумный пример плотного графа, который имеет смысл как граф, а не как relation table.
Спасибо за советы. Именно для таких советов я и писал эту статью.
Про инбридинг надо будет отметить.
Про 10! — это, конечно, не проблема, если надо сравнить 2 графа. А если надо найти граф с 10 вершинами и m ребрами в БД, где много графов с 10 вершинами и m ребрами, то тестировать каждую пару на изоморфизм м.б. затратно.
либо их не нарисовать "наглядно"
Есть наглядные рисунки графов с числом вершин больше 10. Нпр., схема Московского метро — по Вики на настоящий момент — 241 станция (вершина). Но там из самой конструкции следует оптимальное наглядное изображение.
Про трушные графы буду думать. С разумным примером плотного графа, наверное, ничего не выйдет. Даже маленькие деревни — не плотный граф.
https://stackoverflow.com/questions/27437165/what-are-examples-of-naturally-dense-graphs
Пример с cryptocurrencies очень хороший. Направленный, взвешенный, плотный, с несколькими кластерами (соответствующим биржам), и достаточным количеством дыр, чтобы не быть просто таблицей курсов.
И задача сразу рисуется - как из zcash в solana с наименьшими потерями при наименьшем числе хопов попасть.
Добрый день, автор!
Я минусую за это : "Дисклеймер. Далее хочу высказать свое сугубо личное мнение, никого ни в чем, не пытаясь убедить или переубедить. Исключительно в порядке обсуждения. Т.о. я адресуюсь к читателям, уже знакомым с торией графов. "
Да, я бывший преподаватель университета. Да, графы я преподавал. Да, в моей первой статье на Хабре написано, где проходит граница современных исследований. Пожалуйста, не показывайте читателям вашей полной некомпетентности в теории графов - не поймут. Даже отечественные авторы ушли уже далеко вперед от тех "теоретических" предположений, которые вы имели бесчестье тут написать.
Добрый день, читатель!
Да, в моей первой статье на Хабре написано, где проходит граница современных исследований
Не нашел у Вас статьи про графы. Пожалуйста, укажите конкретно.
Даже отечественные авторы ушли уже далеко вперед от тех "теоретических" предположений, которые вы имели бесчестье тут написать.
А можно конкретнее? В чем я не прав?
Даже отечественные авторы ушли уже далеко вперед
Почему "Даже"? Считаете, что все отечественные авторы плохие спецы в теории графов? Я упомянул несколько всемирно известных имен: Адельсон-Вельский, Зыков, Малинины (отец и дочь), Пономаренко, Касьянов и Евстигнеев. Могу еще назвать, но думаю, что упомянутых достаточно. Себя называть не буду, хотя печатаюсь в J of Math Chem, и из J of Graph Theory мне рукописи на рецензию присылают ;) Кое-что написал в ru и en Википедии.
Если отечественные авторы плохие спецы, то как обяснить, что крупные издательства, нпр., Springer издают наши переводные научные журналы и деньги за статьи нашим авторам платят?
Дерево – это граф без циклов. ---- формально, надо вводить ориентацию, чтобы соответствовало рисунку.
Г.М. Адельсон-Вельский доказал, что время поиска по дереву зависит от высоты этого дерева. ---- пожалуйста, дайте определение AVL деревьев, если можно, то и с формулируйте основную теорему поиска. "достаточно развесистое дерево" ускорит поиск. --- в книге Г.М. Адельсон-Вельского есть понятное и простое определение этого факта (да, то самое, на котором я люблю студентов заваливать, там логарифм и округление вверх стоит).
Я (с коллегами) продемонстрировал быстрый поиск при размерности ок.100 лимонов химических... --- может быть, миллионов? Если да, то вам должна быть известны не только правила русского языка, но и теорема об изоморфизме деревьев. Да вот незадача-то, большинство химических соединений имеют не только "древовидное", но и "циклическое" строение. То есть классическая теорема об изоморфизме деревьев не работает. Книга Малининых вряд ли про химию.)
Начало атаки на проблему изоморфизма было сделано тут: Изоморфизм графов с ограниченным параметром /В. Н. Земляченко, Н. М. Корнеенко, Р. И. Тышкевич. - Минск : Институт математики, 1982. - 51 с.-(Препринт ; № 5 (130)), а потом народ как прорвало. Я замечу, что никто сначала не делил проблему изоморфизма между классами графов.
Однако дальше вы пишите: "А проблема изоморфизма графов остается по-прежнему открытой". -- нет, ряд работ наших российских ученых и несколько работ зарубежных ученых опровергают ваши слова.
"Я рисую на сделанном мной инструменте." -- согласен, есть есть сложность в визуализации, если бы вы даже намекнули, что уже составили отрисовки всех органических соединений из справочника Бельштейна, это уже было бы шагом вперед, но есть и более полные справочники. И по реакциям тоже. Например, справочник соединений Американского химического общества.
Далее, если вы считаете, что https://youtu.be/zvXeuxUA98Q нормальное изложение проблемы, то не стоит этим пугать студентов, это же не обзор, а выступление на заданную тему.(
Лучше тогда https://www.ozon.ru/product/grafy-berzha-izomorfizm-dekompozitsiya-raskraski-30041461/ , где точно есть теорема про изоморфизм произвольных графов, и решение задачи 4 красок.
Есть еще множество работ, которые могли бы найти отражение в вашей статье, но не нашли.
Из моей статьи привожу задачу, которая встретилась в собеседованиях.
Задача. За окном стоит береза. На ней, как подсчитали ваши коллеги, 100 000 листьев, диаметр ствола у корня — 60 сантиметров. Запишите указанные параметры в любой математической нотации. И докажите ее пригодность: для переписки с коллегой, так как дерево хотят спилить. Или для компьютерной обработки ее изображения.
Ближе к тематике сайта статья "СТРАТЕГИИ ПРОВЕРКИ КОРРЕКТНОСТИ МЕТОДА ВЫЯСНЕНИЯ ИЗОМОРФИЗМА ГРАФОВ С ИСПОЛЬЗОВАНИЕМ ГРИД-СИСТЕМ НА ДОБРОВОЛЬНОЙ ОСНОВЕ" Э.И. Ватутин, В.С. Титов, где авторы не размахивают руками, а численно проверяют инварианты изморфизмов графов, найденные ими в их более ранних работах.
Спасибо за ответ.
Дерево – это граф без циклов. — формально, надо вводить ориентацию, чтобы соответствовало рисунку.
Формально, не очень удачный рисунок из вики. А где ошибка? Если стрелочки просто линиями заменить, то это дерево останется деревом.
дайте определение AVL деревьев
Надейюсь, из Вики устроит:
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
И что неверного в моей фразе про высоту? Алгоритмы балансировки дерева в обзорной статье, как моя, считаю излишними. Иначе студент не увидит леса из-за сбалансированных деревьев ;)
может быть, миллионов?
Верно. Я использовал вольности языка, принятые на Хабре. А Вы поняли, но придрались.
Да вот незадача-то, большинство химических соединений имеют не только "древовидное", но и "циклическое" строение.
И где я утверждаю обратное? Где сказал, что в органике нет циклов?
Книга Малининых вряд ли про химию.
Да эта книга не про химию. И что из этого следует?
Я замечу, что никто сначала не делил проблему изоморфизма между классами графов.
Я писал не про историю вопроса: что сначала, что потом. Зачем? Может с начала времен начать? Написать, что когда наши предки — пещерные люди выходили на охоту с "кирпичом" на мамонта, они не знали про графы, м.б. только догадывались. Это важно добавить в статью? Те люди хорошо ориентировались на местности — жизнь заставляла, они всегда знали куда бежать, когда на мамонта, а когда от мамонта. Кто не знал — тот не выжил. Но я не об этом пишу. Многие преподы, желая понравиться студентам, начинают с мамонтов и переходят на работы, которые сейчас имеют исторический интерес.
"А проблема изоморфизма графов остается по-прежнему открытой". — нет, ряд работ наших российских ученых и несколько работ зарубежных ученых опровергают ваши слова.
Кто доказал, что изоморфизм 2 графов можно/нельзя найти за полиномиальное время?
Не только я не знаю, но и Вики ;) Читаем:
Хотя задача распознавания изоморфизма графов принадлежит классу NP, неизвестно, является ли она NP-полной или принадлежит классу P (при условии, что P ≠ NP).
Про отдельные классы графов много интересных работ. Нпр., про сильно регулярные графы.
вы даже намекнули, что уже составили отрисовки всех органических соединений из справочника Бельштейна,
В Бельштейне достаточно структурных формул. Зачем там еще что рисовать? Другое дело, что поиск там непростой — студентов специально учат.
Лучше тогда https://www.ozon.ru/product/grafy-berzha-izomorfizm-dekompozitsiya-raskraski-30041461/, где точно есть теорема про изоморфизм произвольных графов, и решение задачи 4 красок.
Про 4 краски не сказал ни слова. Это отдельная тема, про которую еще не так давно спорили — сейчас немного утихли И, да, есть много теорем. Но основной вопрос про изоморфизм остается открытым.
Есть еще множество работ, которые могли бы найти отражение в вашей статье, но не нашли.
Да! Есть! Тогда бы моя статья превысила все мыслимые пределы.
Задача. За окном стоит береза
Не вижу смысла этой задачи. Прошу Вас растолкуйте.
Можно написать: береза: (листьев:100 000; диаметр ствола: 60). И что?
Ближе к тематике сайта статья "СТРАТЕГИИ ПРОВЕРКИ КОРРЕКТНОСТИ МЕТОДА ВЫЯСНЕНИЯ ИЗОМОРФИЗМА ГРАФОВ С ИСПОЛЬЗОВАНИЕМ ГРИД-СИСТЕМ НА ДОБРОВОЛЬНОЙ ОСНОВЕ" Э.И. Ватутин, В.С. Титов
Помню Ватутина по Вики, писали с ним про графы. Оставил отличные впечатления, как спец и как человек. В статье читаем:
Приведено описание стратегий проверки методов выявления изоморфизма графов путем организации попарного сравнения матриц смежности графов выбранной размерности и с использованием построения разбиения на классы изоморфизма, что существенно снижает требуемые вычислительные затраты. Показано, что точная проверка методов возможна только для графов небольшой размерности (N=10).
Далее:
Таким образом, данная стратегия позволяет расширить область проверки до N 9 10
с использованием параллельных вычислительных средств (кластеров, суперкомпьютеров или грид систем), но не более того.
Могу сразу предложить:
При этом на удаленные компьютеры необходима передача данных о множестве кодов матриц смежностидля поиска попарных совпадений инварианта.
Не нужно передавать матрицы — списки смежности гораздо экономнее. И небольшая придирка: авторы пишут "дифференциальную способность", но принято писать "дискриминирующую".
Про использованные индексы (инварианты), типа индекса Рандича, давно известно, что они не полные, но отлаживать методику распределенных вычислений можно и на них, в этом респект авторам!
Добрый день, автор!
Взял несколько дней на "подумать" над вашим ответом, так как он немного глубже поднимает те вопросы, которые мы тут дружно друг другу комментируем.
Начнем с темы статьи "Зачем студентам теория графов"?
Мой ответ на этот вопрос таков. Нужно знать, чем студент дальше будет заниматься. Для этого уже есть все предпосылки - понятия теории графов есть как в школьном учебнике, так и в институте им. Горького - любого гуманитария обучают математике, где графы входят в одобренную Минпросом программу.
Не вижу смысла этой задачи. Прошу Вас растолкуйте. Можно написать: береза: (листьев:100 000; диаметр ствола: 60). И что?
Значит вы лично не проходите собеседование в 90% IT компаний РФ. Задача-то из школьной программы. ) Растолковываю, здесь проверяется с какими (базовыми!) разделами теории графов знаком человек, понимает ли хоть один код графа, работал ли над реальными задачами в IT. Ответов на эту задачу - множество, тем она и хороша для собеседования.
Алгоритмы балансировки дерева в обзорной статье, как моя, считаю излишними. Иначе студент не увидит леса из-за сбалансированных деревьев ;)
Пожалуйста, не надо недооценивать хорошо мотивированных студентов. Основные классы графов есть в приложениях всех современных изданий Ф. Харари, не отстают от них и детские книжки-головоломки. А вот без баланса в нынешнем мире бешеного неравновесия даже графа не нарисуешь (мы же с правильными иерархиями привыкли работать, не так ли?)
Книга Малининых вряд ли про химию.
Да эта книга не про химию. И что из этого следует?
Она не стыкуется с шуровостью, на которой так настаивает Лекция 10 | Проблема изоморфизма графов | Илья Пономаренко | Лекториум, следовательно, в этой книге тоже нет полной драматизма изложения теории изоморфизма не-шуровых структур.
Пожалуйста, не ссылайтесь на русскоязычную часть Вики. Ее пишут простые смертные, а они не всегда в курсе статей за 2010-2015 гг. Работа рецензентом - это хорошо, это дает некоторый кругозор в мире узких специалистов и помогает писать статьи почти на любые темы.
Добрый день, автор!
Доброе время суток, читатель!
Рад, что ответили.
Мой ответ на этот вопрос таков. Нужно знать, чем студент дальше будет заниматься.
Чем студент дальше будет заниматься этого никто не знает.
Значит вы лично не проходите собеседование в 90% IT компаний РФ. Задача-то из школьной программы. ) Растолковываю, здесь проверяется с какими (базовыми!) разделами теории графов знаком человек, понимает ли хоть один код графа, работал ли над реальными задачами в IT. Ответов на эту задачу — множество, тем она и хороша для собеседования.
Я много лет работаю с графами. Не буду грузить химией, повторю про решение
игрушечной задачи. Я знаю разные представления графов: в рисунке, в списке, в матричном виде. Но Ваше объяснение не понял. У меня нет проблемы трудоустройства. Но если 90% IT компаний дают эту задачу — мне жаль соискателей. Я, когда нанимаю, предлагаю более понятное — те же метаграммы. Или индекс Хосойи. Можно поговорить и не про графы — нпр., решето Эратосфена — хорошая тема. Если человек отличает алгоритм от логарифма, то в алгоритмике графов быстро разберется.
Пожалуйста, не ссылайтесь на русскоязычную часть Вики. Ее пишут простые смертные, а они не всегда в курсе статей за 2010-2015 гг.
Я туда писал вместе с упомянутым Вами Ватутиным. Мы в курсе последних статей. (И в англо-вики я писал ;)
Сожалею, но с "шуровостью" не все понял.
Добрый день, автор!
Долго искал вас вне сайта, думаю, что вы из ИОНХ РАН, да и рецензентов русскоязычных в указанных вами журналах из РФ не так много, поэтому мне помогут члены Американского химического общества.
Насчет химии и приложений абсолютно не переживайте - у меня в ней достижений не меньше, чем в математике. Можете смело писать любые формулы, мне их несложно вспомнить. Так как весь мир помешался на поиске активных групп у лекарств, любая структурная статья вызывает кучу интереса.
Насчет шуровости, извините, без цитаты докторской Пономаренко Ильи мне совсем не справится. Гляньте автореферат, пожалуйста. После введения шуровости там есть в самом конце пара теорем, об которые многие уже сломали перья и пальцы.
Личный сайт Ватутина найден и изучен. ) Особенно радует, что он большую часть научной карьеры посвятил оптимизации CUDA для вычисления всего 10 первых членов ряда, дающих число латинских квадратов. Его монографию по оптимизации сейчас читаю, к какому-то выводу еще не пришел.
Для меня решето Эратосфена закончилось как задача тогда, когда было доказано:
Итак, на сегодняшний день человечеству доподлинно известно, что если взять отрезок длиной 246 и сдвигать его вдоль натурального ряда до бесконечности, в нем время от времени будут попадаться пары подряд идущих простых чисел.
К моему большому сожалению, индекс Хосойи у нас спрашивать нельзя, так в химии он - пока что гипотеза (вот тут я опираюсь на Википедию), а для размерности задачи даже среднего уровня (10000 вершин при связности 14-15), на бумажке его не посчитаешь за приемлемое время.
Люблю искать равенства вида 2^15 = 105^2+21743 и спрашивать, как такие найти)).
думаю, что вы из ИОНХ РАН,
Нет, из ИОХ РАН. Им. Зелинского.
Насчет химии и приложений абсолютно не переживайте — у меня в ней достижений не меньше, чем в математике.
Позвольте спросить: в какой химии и в какой математике у Вас достижения? Я не сомневаюсь — просто, если человек работает в кинетике, с ним приходится говорить иначе, чем с квантовиком.
Гляньте автореферат, пожалуйста.
Спасибо. Видел эту работу. Еще раз прочитал. Пономаренко в своих лекциях сделал прекрасный обзор. И его диссер безусловно заслуживает докторской степени. Он очень аккуратно подходит к проблеме изоморфизма графов. Доказывает много важных, но частных случаев. А общего алгоритма и вывода, что полиномиальной сложности не приводит. Что поделать, если задача такая сложная — видимо, ее надо решать частями, как делает Пономаренко. Респект! Все знают аналогию из матана: когда интеграл не берется, его берут по частям :) Может и в случае графов, что-то такое сработает.
если взять отрезок длиной 246 и сдвигать его вдоль натурального ряда до бесконечности, в нем время от времени будут попадаться пары подряд идущих простых чисел.
И что? будут попадаться. Хотите сказать, что решето нужно заменить тестом на простоту ("подтверждающм гребнем")? Даже если и так, то решето имеет большое значение в образовательных целях. И для бенчмаркинга его используют.
Про индекс Хосойи не понял. Почему/зачем его считать на бумажке? CUDA сосчитает быстрее. Связности 14-15 в органике обычно нет (я про степень вершин). В ферроцене формальная 10, но обычно 4. Индекс Хосойи уже десятки лет успешно используют. Конечно, паросочетания для связного графа в 10000 вершин считать не быстро по экспоненте, но был предложен приближенный быстрый способ — логистика проги: можно сделать отсев из 10000 кандидатов, а несколько десятков считать точно. Однако индекс Хосойи не всегда работает, нет гарантии.
Люблю искать равенства вида 2^15 = 105^2+21743 и спрашивать, как такие найти)).
Опять не понял: для чего такие равенства? Предположу, что числа будет проще подобрать по разности логарифмов: 15lg2-2lg105. Я боюсь таких задач: на них можно потратить много времени, получить результаты, но вопрос "зачем?" будет без ответа.
Спасибо за помощь)). Честно говоря очень неожиданно. Рад, что есть люди которые продвигают в массы данные темы!
Зачем студентам теория графов