부호형 그래프

그래프 이론에서 부호형 그래프(signed graph)란 각 변(edge)이 양부호나 음부호를 가지는 그래프를 의미한다.

부호형 그래프는 매 주기마다 에지 부호의 곱이 양수이면 균형을 이룬다. 부호형 그래프의 영단어 "signed graph"라는 이름과 균형의 개념은 1953년 프랭크(Frank Harary)의 수학 논문에서 처음 등장했다. 데네스 코니그(Dénes Kőnig)는 이미 1936년에 다른 용어로 동등한 개념을 연구했지만 기호 그룹의 관련성을 인식하지 못했다. 미시간 대학의 그룹 역학 센터에서 도윈 카트라이트(Dorwin Cartwright)와 프랭크(Harary)는 프리츠 하이더(Fritz Heider)의 심리 삼각형 심리 균형 이론을 부호형 그래프의 심리 균형 이론으로 일반화했다.

부호형 그래프는 관련 없는 영역에서 자연스럽게 많이 등장하기 때문에 여러 번 재발견되었다. 예를 들어, 이것들은 고전적인 루트 시스템의 하위 집합의 기하학을 설명하고 분석할 수 있게 한다. 또, 위상 그래프 이론과 그룹 이론에 나타난다. 그래프의 홀수 및 짝수 주기에 대한 질문에 대한 자연스러운 맥락이다. 비강자성 아이싱(Ising) 모델에서 바닥 상태 에너지를 계산할 때 나타난다. 이를 위해 Σ에서 가장 큰 균형 에지 세트를 찾아야 한다. 상관 클러스터링에서 데이터 분류에 적용되었다.