정점(그래프 이론)

Vertex (graph theory)
맨 왼쪽의 정점 번호 6이 리프 정점 또는 펜던트 정점인 경우 6개의 정점과 7개의 모서리가 있는 그래프

수학에서, 특히 그래프 이론에서, 정점(복수 정점) 또는 노드는 그래프를 형성하는 기본 단위이다: 무방향 그래프는 정점과 가장자리 집합(정점 쌍 순서 없음)으로 구성되는 반면, 방향 그래프는 정점과 호 집합(정점 쌍 순서 있음)으로 구성된다.그래프의 다이어그램에서 정점은 보통 라벨이 있는 원으로 표현되며, 가장자리는 하나의 정점에서 다른 정점으로 연장되는 선 또는 화살표로 표현된다.

그래프 이론의 관점에서 정점은 특징이 없고 분리할 수 없는 개체로 취급되지만, 그래프가 발생하는 응용 프로그램에 따라 추가 구조를 가질 수 있습니다. 예를 들어, 의미 네트워크는 정점이 객체의 개념 또는 클래스를 나타내는 그래프입니다.

모서리를 형성하는 두 정점은 이 모서리의 끝점이라고 하며, 모서리는 정점에 입사한다고 합니다.그래프에 엣지(v,w)가 포함되어 있으면 정점 w는 다른 정점 v에 인접해 있다고 한다.정점 v의 근방은 v에 인접한 모든 정점에 의해 형성된 그래프의 유도 하위 그래프이다.

정점의 종류

A small example network with 8 vertices and 10 edges.
8개의 정점과 10개의 에지가 있는 네트워크의 예.

그래프에서 θ(v)로 표시된 정점의 정도는 정점에 입사하는 가장자리 수입니다.고립된 정점은 도수가 0인 정점, 즉 모서리의 끝점이 아닌 정점입니다(예: 이미지는 하나의 고립된 [1]정점을 나타냅니다).리프 정점(펜던트 정점)은 도수가 1인 정점입니다.유향 그래프에서는, θ +(v)와 θ(v)로 나타나는 integree(착신 에지의 수)를 구별할 수 있다.소스 정점은 indegree가 0인 정점이고 싱크 정점은 outegree가 0인 정점이다.단순한 정점은 네이버가 clique를 형성하는 정점입니다.각 2개의 네이버가 인접해 있습니다.유니버설 정점은 그래프의 다른 모든 정점에 인접한 정점입니다.

잘라낸 정점은 나머지 그래프를 분리하는 정점입니다.정점 구분자는 나머지 그래프를 작은 조각으로 분리하는 정점 집합입니다.k-vertex 연결 그래프는 k개 미만의 정점을 제거하면 항상 나머지 그래프가 연결된 상태로 유지되는 그래프입니다.독립 집합은 인접한 두 개가 없는 정점의 집합이며, 정점 커버는 그래프에서 각 가장자리의 끝점을 적어도 하나 포함하는 정점의 집합이다.그래프의 정점 공간은 그래프의 정점과 일치하는 기저 벡터 집합을 가진 벡터 공간입니다.

그래프는 정점을 다른 정점에 매핑하는 대칭이 있는 경우 정점 추이적입니다.그래프 열거그래프 동형성맥락에서 레이블이 지정된 정점과 레이블이 지정되지 않은 정점을 구별하는 것이 중요하다.레이블이 지정된 정점은 레이블이 지정된 다른 정점과 구별할 수 있는 추가 정보와 연관된 정점입니다. 두 그래프는 레이블이 동일한 정점을 쌍으로 구성하는 경우에만 동형이라고 간주할 수 있습니다.라벨이 부착되지 않은 정점은 그래프 의 인접관계만을 기반으로 다른 정점을 대체할 수 있으며 추가 정보에 기반하지 않습니다.

그래프의 꼭지점은 다면체의 꼭지점과 유사하지만 같지 않다.다면체의 골격은 그래프를 형성하고, 꼭지점은 다면체의 꼭지점이지만, 다면체 정점은 그래프 이론에서는 존재하지 않는 추가적인 구조(기하학적 위치)를 가지고 있다.다면체에서 정점의 꼭지점 도형은 그래프의 꼭지점 근방과 유사합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 파일: Small Network.png; 8개의 정점과 10개의 엣지를 가진 네트워크의 이미지 예시
  • Gallo, Giorgio; Pallotino, Stefano (1988). "Shortest path algorithms". Annals of Operations Research. 13 (1): 1–79. doi:10.1007/BF02288320. S2CID 62752810.
  • Berge, Claude, Théori des Graphes et ses 응용 프로그램.Collection Universitaire de Mathématiques, II Dunod, Paris 1958, vii+277 페이지(영어판, Wiley 1961; Methuen & Co, New York 1962; 러시아어, 모스크바 1961; 스페인어, 멕시코 1962; Roumanian, Bucharest 1969; 중국어, 1963; 제2판)도버, 뉴욕 2001)
  • Chartrand, Gary (1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9.
  • Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
  • Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.
  • Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press. ISBN 0-12-324245-2.

외부 링크