최근 편집
최근 토론
게시판 메인
도구
투표
무작위 문서
스킨 설정
파일 올리기
기타 도구
216.73.216.144
IP
사용자 도구
사용자 설정
로그인
회원 가입
최근 편집
최근 토론
[14:13:01] SCP-1169
[22:34:41] SCP-1168
[22:34:02] 완미적타 : 완벽한 그녀
[22:33:40] 종규전설
[22:33:21] 제광박
[22:32:33] 마오빙창
[22:32:15] 리난
[21:14:42] 리팡후이
[21:05:05] 지아종양
[20:37:38] 수이
돌아가기
삭제
이동
파일 올리기
The Dinitz Problem
(편집) (3)
(편집 필터 규칙)
660,1412
===용어의 정의=== '''Definition''' 그래프 [math(G=(V,E))]에 대하여 색의 집합 [math(C\ (|C|=k))]가 주어졌을 때 각 꼭짓점이 C의 한 색으로 색칠 가능한 [math(k)]의 최솟값을 [math(\chi(G))]라 한다. 각 [math(v \in V)]에 대해 색의 집합 [math(C(v)\ (|C(v)|=k))]가 어떻게 주어져도 각 [math(v)]가 [math(C(v))]의 한 색으로 색칠 가능한 [math(k)]의 최솟값을 [math(\chi_l(G))]라 한다. [math(V’ \subset V)]와 [math(V’)]의 두 원소를 양끝점으로 가지는 변들의 집합 [math(E’ \subset E)]에 대하여 [math(G’=(V’,E’))]을 V’에 의해 induce된 부분그래프라고 한다. '''Definition''' 유향그래프[* 변에 방향이 있는 그래프] [math(\vec{G}=(V,E))]와 [math(v \in V)]에 대하여 [math(v)]를 시작점으로 가지는 변의 개수를 [math(d^{+}(v))]라 한다. 또한, 다음을 만족하는 [math(V)]의 부분집합 [math(K)]를 [math(\vec{G})]의 kernel라고 한다. 1. K는 독립적이다(임의의 두 꼭짓점이 이웃하지 않다). 2. 임의의 [math(u \in V \setminus K)]에 대하여 [math(v \in K)]가 존재하여 [math((u \to v) \in E)]이다.
(임시 저장)
(임시 저장 불러오기)
기본값
모나코 에디터
normal
namumark
namumark_beta
macromark
markdown
custom
raw
(↪️)
(💎)
(🛠️)
(추가)
===용어의 정의=== '''Definition''' 그래프 [math(G=(V,E))]에 대하여 색의 집합 [math(C\ (|C|=k))]가 주어졌을 때 각 꼭짓점이 C의 한 색으로 색칠 가능한 [math(k)]의 최솟값을 [math(\chi(G))]라 한다. 각 [math(v \in V)]에 대해 색의 집합 [math(C(v)\ (|C(v)|=k))]가 어떻게 주어져도 각 [math(v)]가 [math(C(v))]의 한 색으로 색칠 가능한 [math(k)]의 최솟값을 [math(\chi_l(G))]라 한다. [math(V’ \subset V)]와 [math(V’)]의 두 원소를 양끝점으로 가지는 변들의 집합 [math(E’ \subset E)]에 대하여 [math(G’=(V’,E’))]을 V’에 의해 induce된 부분그래프라고 한다. '''Definition''' 유향그래프[* 변에 방향이 있는 그래프] [math(\vec{G}=(V,E))]와 [math(v \in V)]에 대하여 [math(v)]를 시작점으로 가지는 변의 개수를 [math(d^{+}(v))]라 한다. 또한, 다음을 만족하는 [math(V)]의 부분집합 [math(K)]를 [math(\vec{G})]의 kernel라고 한다. 1. K는 독립적이다(임의의 두 꼭짓점이 이웃하지 않다). 2. 임의의 [math(u \in V \setminus K)]에 대하여 [math(v \in K)]가 존재하여 [math((u \to v) \in E)]이다.
비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.
편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이
CC BY 4.0
에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.
전송
미리보기