순서 그래프

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 보다 정확한 인용문을 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2010년 3월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

순서가 지정된 그래프는 노드 상에 총 순서가 있는 그래프다.

순서가 지정된 그래프에서, 노드의 상위 노드는 노드에 인접하고 순서상 노드 앞에 있는 노드들이다.^[1]보다$$ 정확하게는 $n{\displaystyle }$ ${\displaystyle$ n$}$이(가) 순서 그래프 , E, ${\displaystyle \langle$ N$,E,<\rangele$}, 만일${\displaystyle }$(${\displaystyle n}$ ${\displaystyle ,}$ m${\displaystyle }$) ${\displaystyle \in }$ ${\displaystyle E}$ ${\displaystystyle (n,m)\$ $E$ 및$$ n< ${\displaystystystystystystystystystystystyle>$의 $상위{\displaystyle }$ {\daystym}이다.노드의 너비는 부모 수, 순서 그래프의 너비는 노드의 최대 너비다.

순서 그래프의 유도 그래프는 아래에 설명된 방법을 사용하여 순서 그래프에 일부 가장자리를 추가하여 얻는다.순서가 지정된 그래프의 유도 폭은 유도 그래프의 폭이다.^[2]

순서가 지정된 그래프에서 유도 그래프는 다른 노드의 상위 노드인 일부 노드 쌍을 결합하여 얻은 순서가 지정된 그래프다.특히 노드는 주문에 따라 차례로, 마지막에서 첫 번째 순서로 검토한다.각 노드에 대해 부모 중 두 명이 모서리에 연결되지 않은 경우 해당 모서리가 추가된다.즉, 노드 $n{\displaystyle }$ ${\displaystyle n}$을$($를) 고려할 때 $m{\displaystyle }$ ${\displaystyle m}$과 l ${\displaystyle l}$이(가) 상위 항목이고$$ 에지로 결합되지 않은 경우 가장자리$({\displaystyle m}$, ${\displaystyle l}$)$${\$displaystyle(m,l)$가 그래프에 추가된다$$.노드의 부모는 항상 서로 연결되어 있기 때문에 유도 그래프는 항상 화음이다.

예를 들어 순서 그래프의 유도 그래프를 계산한다.순서는 그림에서 노드의 위치로 표현된다: a는 마지막 노드, d는 첫 번째 노드.

원래 그래프.	${\displaystyle a}$의 상위 항목을 고려하여 Edge가 추가됨	$b{\displaystyle }$ ${\displaystyle b}$의 부모를 고려하여 Edge가 추가됨

노드 $a{\displaystyle }$ ${\displaystyle a}$이(가) 먼저 고려된다$$.그것의 부모는 모두 ${\displaystyle a}$에 가입되어 있고 둘$$ 다 주문에서$$ ${\displaystyle a}$보다 앞서 있기 때문에 $b{\displaystyle }$ ${\displaystyle$ $b$$}$과 c ${\displaysty$ c$}$이다$.$엣지가 붙어 있지 않기 때문에 하나가 더해진다.

노드 $b{\displaystyle }$ ${\displaystyle b}$은(는) 두 번째로 간주된다$$.이 노드는 원래 그래프에서 상위 항목으로$$ $d{\displaystyle }$ ${\displaystyle d}$만 포함하지만 부분 빌드된 유도 그래프에서 상위 $항목$으로 c ${\displaystyle c}$도 포함시킨다.실제로, $c{\displaystyle }${\$displaystyle c$}은(는) b$${\$displaystyle$b}에 연결되고$$ 주문$$ 시 $b{\displaystyle }$ ${\displaystyle$ b$}$보다 앞서는 경우도 있다.그 결과 $c{\displaystyle }${\$displaystyle c$} $및$ d$${\$displaystyle d}$ 에지 결합이 추가된다$$.

$d{\displaystyle }$ ${\displaystyle d}$을(를) 고려해도$$ 이 노드에 부모가 없으므로 변경 사항이 발생하지 않는다.

노드 처리 순서가 중요한데, 도입된 가장자리는 새로운 부모를 만들 수 있으며, 새로운 가장자리의 도입과 관련이 있다.다음 예는 다른 순서가 동일한 원본 그래프의 다른 유도 그래프를 생성한다는 것을 보여준다.순서는 위와 동일하지만 $b{\displaystyle }$ ${\displaystyle b}$과 $c{\displaystyle }$ ${\displaystyle c}$이(가) 교환된다.

동일한 그래프지만 $b{\displaystyle }$ ${\displaystyle b}$ 및 $c$ ${\displaystyle c}$의 순서가 바뀜	${\displaystyle a}$을(를) 고려한 후 그래프

앞의 경우와 마찬가지로 $b{\displaystyle }$ ${\displaystyle b}$과 $c{\displaystyle }$ ${\displaystyle c}$은(는) ${\displaystyle a$의 부모다$$.따라서, 그들 사이에 가장자리가 추가된다.새 순서에 따르면 고려되는 두 번째 $노드$는 c ${\displaystyle$ c$}$이다$.$이 노드는 상위(${\displaystyle }$ ${\displaystyle$ b$})$가 하나뿐입니다.$$따라서 새로운 가장자리는 추가되지 않는다.$세{\displaystyle }$ 번째로 고려되는 노드는 b ${\displaystyle b}$이다$.$유일한 부모는 $d{\displaystyle }$ ${\displaystyle d}.$실제로 $b{\displaystyle }$ ${\displaystyle b}$과 $c{\displaystyle }$ ${\displaystyle c}$은(는) 이번에 가입하지 않았다$$.그 결과 새로운 엣지가 도입되지 않는다.$d{\displaystyle }$ ${\displaystyle d}$에도 상위 항목이 없기$$ 때문에 최종 유도 그래프는 위 그래프와 같다.이 유도 그래프는 이전 주문에서 생산된 그래프와 다르다.

참고 항목

• 방향 그래프
• 국소 일관성

참조

• Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7