최근 편집
최근 토론
게시판 메인
도구
투표
무작위 문서
스킨 설정
파일 올리기
기타 도구
216.73.216.107
IP
사용자 도구
사용자 설정
로그인
회원 가입
최근 편집
최근 토론
돌아가기
삭제
이동
파일 올리기
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로 저작자 표시가 충분하다는 것에 동의하는 것입니다.
전송
미리보기
