Википедия
В теории графов зигзаг-произведение регулярных графов G, H (обозначается G ∘ H) берёт большой граф G и маленький граф H и создаёт граф, примерно наследующий размер большого графа, но степень малого. Важным свойством зигзаг-произведения является то, что для хорошего экспандера H распространение результирующего графа лишь слегка хуже распространения графа G.
Грубо говоря, зигзаг-произведение G ∘ H заменяет каждую вершину графа G копией графа H и соединяет вершины, делая малый шаг (zig) внутри облака, а затем большой шаг (zag) между двумя облаками, и ещё один малый шаг внутри конечного облака.
Зигзаг-произведение введено Рейнгольдом, Вадханом и Вигдерсоном. Зигзаг-произведение первоначально использовалось для явного конструирования экспандеров и экстракторов постоянной степени. Позднее зигзаг-произведение использовано в теории вычислительной сложности для доказательства равенства и .