It&#39;s all in your mind

Ага, у нас в лагере была книжка типа "как рассказывать детям о графах" - половина бравших её в руки родителей было уверено, что это о графьях, князях, их интересовало лишь, кому пришло в голову писать отдельную книгу именно о графах. На самом деле (как и в этом посте), это был набор точек, часть из которых соединена рёбрами (https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)) ;-)

From:

Гуманитарии, гы-гы! :)

From:

Собственно, для N = 1 граф - это одна списка (две вершины, одно ребро, в каждой вершине по одному ребру). Для N = 2 - равносторонний треугольник (три вершины, три ребра, в каждой вершине по два ребра). Для трёх ещё реально самому нарисовать, хотя и нетривиально. А если ты сама нарисуешь для четырёх, я тебе памятник в нашей песочнице поставлю ;-)

From:

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

а где есть картинка для валентности 4 ?

From:

Если склеить рога спичкой, то у рога будет валентность 2. Если потом две фигни склеить по рогам, то в точке склейки будет уже 4, нет разве?

Минимальное решение состоит из 8 точек и выглядит как развёртка куба, только две перекладины убраны (иначе - пересечения граней), а вместо них поставлены две диагонали для граней "куба".

А для N = 4 решение (не доказано, что минимальное) есть в Википедии (https://fr.wikipedia.org/wiki/Graphe_de_Harborth). Оно хотя бы симметричное, в статье потом переходят на ограничения "без треугольников, без квадратов", и там начинают лезть такие красавцы!

From:

"склеить по рогам" точнее вдоль перемычки

--<|>--
чота такое

Edited Date: 2015-01-09 02:27 pm (UTC)

From:

Да, понял, вполне решение. Не минимальное - загибаться долго будет, - но решение.

From:

четыре штуки, в сумме 20 вершин и 28 рёбер

From:

Даже трёх достаточно, но всё равно больше 8 вершин выходит.

From:

да, точно, протупил, мне повсюду чудятся углы по 120 градусов, а там 150

From:

son-de-la-voix.livejournal.com

Минимальное из таких же штук и состоит. Только загибать надо правильно:
https://upload.wikimedia.org/wikipedia/ru/thumb/d/dc/Matchstick-3-regualar.svg/150px-Matchstick-3-regualar.svg.png

From:

Ой, точно :-) Я тупой, две картинки рядом держал - и не заметил!

From:

Что такое "длина графа"?

From:

Вы с Томой издеваетесь?! Спички одинаковой длины :-)

From:

Я есть плёхо гофорить по-рюсски сегодня. :) Вместо "спичек одинаковой длины" прочитал "одинаковой длины граф". Вот она, неоднозначность положения слов в предложении! :)
Я прям подумал, может, во французской теории графов есть понятие длины графа. :)))

Edited Date: 2015-01-09 03:26 pm (UTC)

From:

Да я понял :-) Но в контексте смотрелось хорошо.
[offtopic] Меня мальчик вчера спросил, когда вы к нам в гости приедете :-) Пора начинать думать, я так считаю!

From:

Нет, ну длины там разные вводятся регулярно, вне зависимости от страны - самый длинный из самых коротких, связывающих две точки и т.п. Но я бы тогда уточнил :-)
Пошёл ставить запятые в пост.

From:

Но это ж будет путь или маршрут (в зависимости от того, направленный граф или нет). Вернее, длина пути или маршрута.
Есть, конечно, ещё понятие диаметра графа, но не длины.

From:

О, точно, диаметр :-)

From:

Вот две вещи: теория графов и нейросети (вплотную, кстати, связанные) вызывают у меня нежные воспоминания об учёбе в студенческие годы. :)

From:

Сейчас придёт Хомка и спросит, что такое спички?

From: