둘러보기 메뉴
검색
바뀐글
임의글
개인 도구
가입하기
로그인
도움말
도움말
질문게시판
자주 묻는 질문
커뮤니티
실시간 채팅방
가입인사게시판
자유게시판
뉴스게시판
제재안게시판
최근 토론
페미위키
공지사항
개선 요청
바뀐글
임의글
파일 올리기
다면 분류 목록
특수 문서 목록
매트로이드 문서 원본 보기
이름공간
문서
토론
주시
도구
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
위키베이스 항목
행위
보기
읽기
원본 보기
역사 보기
←
매트로이드
문서 편집 권한이 없습니다. 다음 이유를 확인해주세요.
요청한 명령은 다음 중 하나의 권한을 가진 사용자에게 제한됩니다:
사용자
,
Seeders
.
문서를 고치려면 이메일 인증 절차가 필요합니다.
사용자 환경 설정
에서 이메일 주소를 입력하고 이메일 주소 인증을 해주시기 바랍니다.
문서의 원본을 보거나 복사할 수 있습니다.
매트로이드 Matroid ==개요== 선형독립을 조합론적으로 정의한 개념. 보다 자세히 알고 싶은 사람은 다음 [https://www.math.lsu.edu/~oxley/survey4.pdf 링크]를 참고하자. ==정의== 어떤 유한 집합 <math>E</math>와 <math>\mathcal{I} \subseteq 2^E</math>(<math>2^E</math>는 <math>E</math>의 멱집합을 의미한다.)에 대해 <math>(E, \mathcal{I})</math>가 매트로이드 임은 다음을 만족함을 의미한다: # <math>\emptyset \in \mathcal{I}</math> # (유전성, hereditary) <math>X \in \mathcal{I}</math>이고 <math>Y \subseteq X</math>이면 <math>Y \in \mathcal{I}</math> # (추가성, augmentation property) <math> X, Y \in \mathcal{I}</math>이고, <math> |X| < |Y|</math>이면, 어떤 <math> e \in Y - X</math>가 존재해 <math> X \cup \{e\} \in \mathcal{I} </math> 매트로이드도 그래프와 마찬가지로 가중치를 부여해 생각할 수도 있다. 이 경우, <math>E</math>의 각 원소에 실수만큼 가중치를 주고, <math>E</math>의 각 부분집합의 가중치는 해당 부분집합의 원소들의 가중치의 합으로 생각해주면 된다. 대개 <math>e \in E</math>의 가중치를 <math>w(e)</math>로 표기한다. ==예시== ===벡터 매트로이드=== [[체]] <math>\mathbb{F}</math> 상의 <math>m \times n</math> 행렬 <math>A</math>가 있다고 하자. <math> [n] (=\{1, 2, \cdots, n\})</math>의 부분집합 <math>X</math>에 대해 <math>A[X]</math>를 <math>X</math>에 속하는 열만을 택해 만든 새로운 (<math>m \times |X|</math> 크기의) 행렬이라 하자. <math>\mathcal{I} = \{ X \in 2^{[n]} : A[X]\text{의 열벡터들이 선형독립}\}</math>으로 정의할 경우, <math>([n], \mathcal{I})</math>는 매트로이드가 된다. 증명은 추가 바람. ===그래프 매트로이드=== 그래프 <math>G = (V, E)</math>[* 단순 그래프일 필요는 없다.]가 주어졌을 때, <math>\mathcal{I} = \{X \in 2^E : X\text{에 속하는 간선들에 의한 유도 부분 그래프가 사이클을 포함하지 않음} \}</math> 로 정의하면, <math>(E, \mathcal{I})</math>가 매트로이드가 된다.
매트로이드
문서로 돌아갑니다.
다른 언어