그래프에서 일치

Question

최대 n/4의 카디널리티 일치를 갖는 그래프를 찾으려면 어떻게해야합니까? 또는 n/3라고 말하고 싶습니까? 여기서 n은 그래프의 정점 수를 나타냅니다. 연결된 그래프가 가능합니까?

Answer 1

가장 간단한 예로는 complete bipartite graph K_m,n입니다. 일치하는 크기를 일정 비율 (|V|/k)이되도록 조정하려면 |V| = n + m = 2*k*m부터 (2*k-1)*m이어야하고 일치하는 크기는 2*m이어야합니다. 은 (2*k-1)*m이어야합니다.

Answer 2

Tutte Berge formula을 기반으로 그래프를 구성 할 수 있습니다. 이것을 사용하여 다음과 같이 최대 일치 크기 n/4로 그래프를 구성 할 수 있습니다. V를 그래프의 꼭지점 집합이라고하고 U를 모든 꼭지점의 부분 집합이라고합시다. k- | U | > = | V |/2이다. VU로부터 홀수 크기의 컴포넌트 C1, C2, ..., Ck (서로 분리되어 있음)를 만들고 각 Ci의 모든 에지 세트를 U의 꼭지점에 추가하십시오.

C1, ... , Ck는 우리가 U를 삭제할 때 얻는 이상한 크기의 구성 요소라고 가정한다. {U, C1, ..., Ck}의 다른 꼭지점들은 위의 제약 조건에 따라 어떤 식 으로든 연결될 수있다.