Статья
Теория графов: структуры, свойства и теоремы
От строгого определения графа до теорем Эйлера, Куратовского, Кёнига и Кирхгофа — с интуицией, ручными разборами и работающим Python-кодом.
База знаний
Тема: Графы
9 материалов в этой теме.
Материалы
9 на странице
Статья
Система непересекающихся множеств (DSU)
Как двумя массивами и двадцатью строками кода получить структуру, которая отвечает на вопрос «связаны ли эти два объекта» практически за константу.
Статья
Остовные деревья и потоки в сетях
Два столпа сетевой оптимизации: минимальное остовное дерево через свойства разреза и цикла, и максимальный поток через остаточную сеть, теорему о минимальном разрезе и …
Статья
Обходы графов: BFS, DFS, топологическая сортировка, компоненты
Один каркас обхода, из которого вырастают BFS, DFS, топологическая сортировка, компоненты связности, SCC и мосты: интуиция, доказательства корректности, итеративные …
Статья
Кучи и приоритетные очереди
Как из обычного массива получается структура, которая всегда знает свой минимум: инвариант кучи, sift-up и sift-down, построение за O(n), heapsort, d-арные и Фибоначчиевы …
Статья
Кратчайшие пути: Дейкстра, Беллман–Форд, Флойд–Уоршелл, A*
Одна операция релаксации порождает всё семейство алгоритмов кратчайших путей: разбираем условия корректности каждого, доказательства, реализации, потенциалы и …
Статья
Графы: представления, свойства и выбор структуры
Как хранить граф в памяти: список рёбер, матрица и списки смежности, CSR; чем они различаются по времени, памяти и локальности, как извлекать базовые свойства графа и как …
Статья
Графовые нейронные сети
Как обучать нейросети на данных без сетки и без порядка: перестановочная симметрия, передача сообщений, GCN/GraphSAGE/GAT/GIN, пределы выразительности, переглаживание и …
Статья
Графовые и key-value БД: Neo4j, Dgraph, etcd, RocksDB, LMDB
Два семейства, стоящих на противоположных краях спектра абстракции: движки ключ-значение, из которых собраны почти все остальные БД, и графовые СУБД, где связь — …
По этому запросу ничего не найдено.