Рубрика «графы»

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

Охота на недостающий тип данных - 1

Все графы созданы с помощью graphviz (источник)

В сфере разработки ПО графы используются повсеместно:

  1. Зависимости пакетов, как и импорт модулей, формируют направленные графы.
  2. Интернет — это граф, состоящий из ссылок между веб-страницами.
  3. При проверке моделей анализ выполняется путём изучения «пространства состояний» всех возможных конфигураций. Узлы — это состояния, а рёбра — это допустимые переходы между ними.
  4. Реляционные базы данных — это графы, в которых узлы являются записями, а рёбра — внешними ключами.
  5. Графы — это обобщение связанных списков, двоичных деревьев и хэш-таблиц.1

Кроме того, графы также широко используются в бизнес-логике. Научные работы со ссылками формируют графы цитат. Транспортные сети представляют графы маршрутов. Социальные сети — это графы связей. Если вы работаете в сфере разработки, то рано или поздно встретитесь с графами.

Я вижу графы повсюду и использую их для анализа всевозможных систем. В то же время я побаиваюсь использовать их в коде. Какой из популярных языков программирования ни возьми, поддержка графов в них практически отсутствует. Ни в одном её нет в виде встроенного типа, очень мало где они прописаны в стандартной библиотеке, и у многих языков нет для этой функциональности надёжного стороннего пакета. Чаще всего мне приходится создавать графы с нуля. Существует большой разрыв между тем, как часто инженерам ПО могут понадобиться графы и тем, в какой степени экосистема их поддерживает. Где все графовые типы?Читать полностью »

Ответом на задачу по упаковке цветов в бесконечной сетке оказалось число 15 - 1

Видео

В задаче по «упаковке цветов графа» (в оригинале packing coloring, — прим. пер.) спрашивается, сколько чисел необходимо для заполнения бесконечной сетки так, чтобы идентичные числа никогда не оказывались слишком близко друг к другу. И новый арифметический эксперимент с использованием компьютера даёт на удивление простой ответ.

Сколько чисел потребуется для заполнения бесконечной сетки так, чтобы расстояние между вхождениями одного числа было больше самого этого числа?Читать полностью »

Результирует ли случайный граф в треугольник (справа), гамильтонов цикл (в центре) или проявит какие-либо иные интересующие нас свойства?
Результирует ли случайный граф в треугольник (справа), гамильтонов цикл (в центре) или проявит какие-либо иные интересующие нас свойства?

Читать полностью »

В данной статье для реализации алгоритма будут рассмотрены:

  1. Система хранения графа на основе List<>

  2. Сортировка рёбер графа по весу

  3. Система непересекающихся множеств


Алгоритм Краскала необходим для нахождения минимального остовного дерева графа.

О чём речь?

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

Читать полностью »

Предлагаю обсудить философскую тему. Что если представить нашу жизнь как взвешенный ориентированный ациклический граф? Визуализация графа приведена на рисунке:

Жизнь как граф - 1

РЧитать полностью »

Какое произведение киноискусства оставило самый большой отпечаток в современной поп культуре? Предлагаю подумать над этим вопросом некоторое время. Может быть это Апокалипсис сегодня? Или Крестный отец? А вдруг главный фильм всех времен и народов это шедевр отечественного кинематографа - фильм Викинг?

К счастью, это можно посчитать.

Отсылки в современных произведениях популярного искусства - забавная вещь. Люди их любят. Возьмем популярный мультсериал Читать полностью »

Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор

В этой статье:

Матрица смежности

Матрица инцидентности

Список смежности (инцидентности)

Взвешенный граф (коротко)

Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.

Матрица является удобной для представления плотных графов в которых количество ребер (E) примерно равно количеству вершин (V).

Читать полностью »

Два специалиста по информатике нашли в весьма неожиданном месте идею, которая как раз пригодилась им для прорыва в теории графов

Новый алгоритм проверки пересечений в графах прятался на виду - 1

В октябре 2019 Джейкоб Холм и Ева Ротенберг пролистывали работу, опубликованную ими за несколько месяцев до этого – и вдруг поняли, что наткнулись на нечто серьёзное.

Десятилетиями специалисты по информатике пытались разработать быстрый алгоритм для определения того, можно ли добавить к определённому графу рёбра так, чтобы он остался «планарным» – то есть, чтобы его рёбра не пересекались. Однако ни у кого не получалось улучшить алгоритм, опубликованный более 20 лет назад.

Холм и Ротенберг с удивлением обнаружили, что в их работе есть идея, позволявшая достаточно сильно улучшить этот алгоритм. Она «разобралась с одним из главных препятствий на пути к реальному алгоритму», — сказал Холм, специалист по информатике из Копенгагенского университета. «Возможно, мы полностью раскрыли этот вопрос».
Читать полностью »

Переведя гипотезу Келлера на понятный компьютерам язык поиска в графах, исследователи, наконец, решили задачу покрытия пространств плиткой

Компьютерный поиск помог разобраться с 90-летней математической задачей - 1

Команда математиков, наконец, разобралась с гипотезой Келлера – однако не своими силами. Вместо этого они обучили целый парк компьютеров, и те решили её.

Гипотеза Келлера, выдвинутая 90 лет назад Отт-Генрихом Келлером, связана с задачей покрытия пространств идентичными плитками. Она утверждает, что если замостить двумерное пространство двумерными квадратными плитками, то хотя две из них должны будут соприкасаться сторонами. То же предсказание гипотеза делает для любых измерений – то есть, при заполнении 12-мерного пространства 12-мерными «квадратами», хотя бы у двух из них должна будет найтись общая сторона.

Годами математики бились над этой гипотезой, доказывая её истинность для одних измерений и ложность для других. И к прошлой осени вопрос оставался нерешённым только для семимерного пространства.
Читать полностью »

image

Введение

Для печати на клавиатуре необходимо неподвижно сидеть или стоять. Геймпады, в отличие от них, портативные и компактные. Управляя ими, можно ходить по комнате или прилечь на диван.

Из-за малого количества кнопок на геймпаде никто не рассматривал их как средство ввода объёмных текстов, например, в программировании.

Однако аналоговые стики (а у большинства геймпадов их два) имеют потенциал обеспечения бесконечного количества вариантов ввода. Вопрос сводится к выбору подходящих жестов для максимальной эффективности и минимального напряжения больших пальцев.

Для геймпадов существует множество способов ввода текста. Если вы когда-нибудь играли в консольные игры, то, скорее всего, использовали какой-то из них.

Может ли геймпад заменить клавиатуру? Пробуем программировать на стиках - 2

Экранный ввод текста в Legend of Zelda

В Legend of Zelda игрок должен по очереди выбирать буквы при помощи крестовины со стрелками и каждый раз нажимать кнопку подтверждения для добавления буквы в поле ввода текста.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js