В теории графов проводимость из графа G = ( V , E ) меры , как «хорошо вяжут» граф: он контролирует , как быстро случайное блуждание на G сходится к своему стационарному распределению . Проводимость графа часто называют константой Чигера графа как аналога его аналога в спектральной геометрии . [ необходима цитата ] Поскольку электрические сети тесно связаны со случайными прогулками с давней историей использования термина «проводимость», это альтернативное название помогает избежать возможной путаницы.
Проводимость разреза в графе определяется как:
где - элементы матрицы смежности для G , так что
это общее число (или вес) ребер , инцидентных с S . также называется объемом множества .
Проводимость всего графика - это минимальная проводимость по всем возможным разрезам:
Эквивалентно проводимость графика определяется следующим образом:
Для d -регулярного графа проводимость равна изопериметрическому числу, деленному на d .
Обобщения и приложения
В практических приложениях часто учитывают проводимость только над разрезом. Обычное обобщение проводимости - рассмотрение случая весов, присвоенных ребрам: затем веса добавляются; если вес имеет форму сопротивления, то добавляются обратные веса.
Понятие проводимости лежит в основе изучения перколяции в физике и других прикладных областях; таким образом, например, проницаемость нефти через пористую породу может быть смоделирована в терминах проводимости графика с весами, заданными размерами пор.
Проводимость также помогает измерить качество спектральной кластеризации . Максимум среди проводимости кластеров обеспечивает границу, которую можно использовать вместе с межкластерным весом ребер для определения меры качества кластеризации. Интуитивно понятно, что проводимость кластера (который можно рассматривать как набор вершин в графе) должна быть низкой. Помимо этого, также может использоваться проводимость подграфа, индуцированная кластером (называемая «внутренней проводимостью»).
Цепи Маркова
Для эргодической обратимой цепи Маркова с нижележащим графом G проводимость - это способ измерить, насколько сложно оставить небольшой набор узлов. Формально проводимость графа определяется как минимум по всем множествамиз емкости вделится на эргодический поток из. Алистер Синклер показал, что проводимость тесно связана со временем перемешивания в эргодических обратимых цепях Маркова. Мы также можем рассматривать проводимость более вероятным образом, как минимальную вероятность выхода из небольшого набора узлов, учитывая, что мы начали с этого набора с самого начала. Письмо для условной вероятности выхода из набора узлов S с учетом того, что мы изначально находились в этом наборе, проводимость является минимальной над наборами которые имеют общую стационарную вероятность не более 1/2.
Электропроводность связана со временем перемешивания цепи Маркова в обратимой настройке.
Смотрите также
Рекомендации
- Бела Боллобас (1998). Современная теория графов . GTM . 184 . Springer-Verlag . п. 321. ISBN. 0-387-98488-7.
- Kannan, R .; Vempala, S .; Ветта, А. (май 2004 г.). «О кластеризации: хорошее, плохое и призрачное» (PDF) . J. ACM . 51 (3): 497–515. DOI : 10.1145 / 990308.990313 .
- Фань Чанг (1997). Теория спектральных графов . Конспект лекций CBMS. 92 . Публикации AMS. п. 212. ISBN. 0-8218-0315-8.
- А. Синклер. Алгоритмы случайной генерации и подсчета: подход цепей Маркова. Бирхаузер, Бостон-Базель-Берлин, 1993.
- Д. Левин, Ю. Перес , Е. Л. Вильмер : Марковские цепи и времена перемешивания