메쉬드 계수

그래프 이론에서 중수 계수는 정점 수가 동일한 다른 평면 그래프의 가능한 면 수의 일부로 그래프의 경계면 수를 측정하는 평면 그래프의 상수 그래프입니다.트리의 경우 0부터 최대 평면 그래프의 경우 1까지입니다.^[1][2]

정의

중간도 계수는 연결된 평면 그래프의 일반적인 사이클 구조를 두 개의 극단적 관련 참조와 비교하는 데 사용된다.한 쪽 끝에는 순환이 없는 나무, 평면 그래프가 있다.^[1]다른 극한은 최대 평면 그래프, 주어진 정점 수에 대한 가장 높은 가장자리 수와 면의 평면 그래프로 표현된다.정규화된 중상도 계수는 그래프에서 가능한 최대 얼굴 주기에 대한 사용 가능한 얼굴 주기의 비율이다.이 비율은 트리의 경우 0이고 최대 평면 그래프의 경우 1이다.

보다 일반적으로, 모든 n-vertex 평면 그래프는 최대 2n - 5개의 경계면(한 개의 경계면 제외)을 가지며, m 가장자리가 있을 경우 경계면 수는 m - n + 1(그래프의 회로 순위와 동일)이라는 것을 오일러 특성을 사용하여 나타낼 수 있다.따라서 정규화된 중수 계수는 다음 두 숫자의 비율로 정의할 수 있다.

${\displaystyle \cHB ={\frac {m-n+1}{2n-5}.}$

나무의 경우 0에서 최대 평면 그래프의 경우 1까지 다양하다.

적용들

중간도 계수는 네트워크의 중복성을 추정하는 데 사용될 수 있다.이 매개변수는 네트워크의 건전성을 측정하는 대수적 연결성과 함께 물 분배 네트워크에서 네트워크 회복성의 위상학적 측면을 정량화하는 데 사용될 수 있다.^[3]또한 도시 지역의 거리의 네트워크 구조를 특성화하는 데도 이용되어 왔다.^[4][5][6]

제한 사항

${\displaystyle \mathrm{평균}}$ 도 $⟨{\displaystyle }$ ${\displaystyle ⟨}$= ${\displaystyle 2}$ ${\displaystyle m}$/ ${\displaystyle n}$ ${\displaystyle \langle k\angle =2m/n$의 정의를 사용하면 큰 그래프 한계(가장자리 수 $n{\displaystyle }$ ${\displaystyle \gg }$ ${\displaystyle 1}$ ${\displaystyn n\g$ 1)에서$$메쉬드(meshedity)가 다음과 같은 경향이 있음을 알 수 있다.

${\displaystyle \cHB \cHB \cHB {\langle k\angle }{4}-{4}-{\frac {1}{2}}:}$

따라서 큰 그래프의 경우 중간 정도는 평균 정도보다 더 많은 정보를 전달하지 않는다.

참조