403
правки
Изменения
→Алгоритм
{{Теорема
|statement=
Пусть <tex>\Sigma</tex> {{---}} множество слабо пересекающихся сайтов, <tex>p</tex> {{---}} точка, <tex>p \notin \Sigma</tex>. Тогда <tex>\partial R_\Sigma(p)</tex> {{---}} связная кривая, содержащая более одной точки.
|proof=
Пусть <tex>C = V(p, \Sigma \cup \{p\})</tex>, <tex>R_\Sigma(p) = \varepsilon</tex>.
Пусть <tex>\varepsilon_1, \varepsilon_2, ... , \varepsilon_k</tex> {{---}} связные компоненты <tex>\varepsilon</tex> для некоторого <tex>k</tex>.
Предположим, что <tex>k \ge 2</tex>. Тогда cуществует путь <tex>P \subseteq C \setminus \varepsilon</tex>, соединяющий две точки <tex>x</tex> и <tex>y</tex> на границе <tex>C</tex> и отделяющий <tex>\varepsilon_1</tex> от <tex>\varepsilon_2</tex>. <tex>P \cap \varepsilon = \emptyset varnothing \Rightarrow P \cap V_1^\circ(\Sigma) = \emptyset varnothing \Rightarrow P \subseteq V(s, \Sigma)</tex> для некоторого <tex>s \in \Sigma</tex>. <tex>x, y \in P \Rightarrow</tex> все достаточно малые окрестности <tex>U(x)</tex>, <tex>U(y)</tex> полностью содержатся в <tex>V(q, \Sigma)</tex>. Значит, точки пересечения этих окрестностей с дополнением <tex>C</tex> лежат в <tex>V(q, \Sigma \cup p)</tex> и могут быть соединены путём <tex>L \subseteq V(q, \Sigma \cup \{p\}) \subseteq V(q, \Sigma)</tex>. Следовательно, цикл <tex>P \circ L</tex> полностью содержится в <tex>V(q, \Sigma)</tex> и содержит <tex>\varepsilon_1</tex> и <tex>\varepsilon_2</tex> в своей внутренности. Это противоречие, следовательно <tex>k = 1</tex>.
}}
Таким образом, для нахождения области конфликтов, можно найти одно конфликтующее ребро, а затем, при помощи DFS, найти все остальные.
