목차
25 처지: 동치, 라게르 다항식, 경로 (그래프 이론), 경로 그래프, 분배 함수 (통계역학), 부분 순서 집합, 그래프, 그래프 이론, 대칭차, 평면 그래프, 이합체 모형, 일반화 페테르센 그래프, 집합, 집합의 크기, 유기화학, 윌리엄 토머스 텃, 파프 방향, 생성함수 (수학), 샤프-P-완전, 순환 그래프, 에르미트 다항식, 연결 공간, 완전 그래프, 완전 이분 그래프, P (복잡도).
- 그래프 이론의 계산 문제
- 다항 시간 문제
- 조합 최적화
동치
수학과 논리학에서 동치(同値)란 두 문장이 논리적으로 같다는 것을 의미.
라게르 다항식
르 다항식의 그래프 수학에서, 라게르 다항식(Laguerre多項式)은 직교 관계를 만족시키는 일련의 다항식들이.
경로 (그래프 이론)
이론에서, 경로(經路)는 같은 꼭짓점을 거듭 거치지 않는 변들의 열이.
경로 그래프
경로 그래프 P_6 그래프 이론에서, 경로 그래프(經路graph)는 모든 꼭짓점의 차수가 2 이하인 나무이.
분배 함수 (통계역학)
통계 역학에서, 분배 함수(分配函數) Z는 열역학적 평형에 있는 계의 통계적 성질을 계산하는 데 쓰는 중요한 개념이.
부분 순서 집합
''y'', ''z'') 순서가 정해지지 않은 것이다. 순서론에서, 부분 순서(部分順序) 또는 반순서(半順序)는 순서·나열 등의 개념을 추상화한 이항 관계이.
그래프
6개의 꼭짓점과 7개의 변을 갖는 그래프 수학에서, 더 구체적으로 그래프 이론에서, 그래프()는 일부 객체들의 쌍들이 서로 연관된 객체의 집합을 이루는 구조이.
그래프 이론
6개의 꼭짓점과 7개의 변을 갖는 그래프 그래프 이론(graph理論)은 수학에서 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프에 대한 연구이.
대칭차
벤 다이어그램으로 표현한 대칭차 A\,\triangle\,B 집합론에서, 두 집합 A,B의 대칭차(對稱差, 또는 대칭차집합)는 둘 중 한 집합에는 속하지만 둘 모두에는 속하지는 않는 원소들의 집합이.
평면 그래프
평면 그래프(planar graph)는 평면 상에 그래프를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 그래프를 의미.
이합체 모형
통계역학과 그래프 이론에서, 이합체 모형(二合體模型)은 어떤 그래프 위의 완벽 부합들의 공간 위에 정의되는 통계역학 모형이.
일반화 페테르센 그래프
이론에서, 일반화 페테르센 그래프(一般化Petersen graph)는 같은 수의 꼭짓점을 갖는 정다각형과 별 모양에서 대응하는 꼭짓점들을 이어 얻는 그래프이.
집합
9개의 다각형의 집합을 나타낸 오일러 다이어그램 수학에서, 집합(集合)은 명확한 기준에 의하여 주어진 서로 다른 대상들이 모여 이루는 새로운 대상이.
집합의 크기
집합론에서, 집합의 크기() 또는 농도(濃度)는 집합의 "원소 개수"에 대한 척도이.
유기화학
메테인 분자 구조: 가장 단순한 탄화수소 화합물 유기화학(有機化學, Organic chemistry)은 유기 화합물의 구조나 특성, 제법 및 응용등을 연구하는 화학의 한 분야이.
윌리엄 토머스 텃
윌리엄 토머스 텃(1917–2002)은 영국 태생의 수학자이.
파프 방향
이론에서, 파프 방향(Pfaff方向)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이.
생성함수 (수학)
수학에서 어떤 수열 an (n은 자연수)에 대하여, 와 같이 미지수의 계수가 수열의 각 항으로 되어 있는 멱급수 형태의 함수를 생성함수(generating function).
샤프-P-완전
산 복잡도 이론에서 #P-완전은 복잡도 종류의 일종이.
순환 그래프
순환 그래프 C_6 그래프 이론에서, 순환 그래프(循環graph)는 정다각형의 그래프이.
에르미트 다항식
확률론 에르미트 다항식 H_n(x)의 그래프 (n.
연결 공간
A는 유클리드 평면의 연결 부분 공간이며, B는 비연결 부분 공간이다. 일반위상수학에서, 연결 공간(連結空間)은 공집합이 아닌 두 열린집합으로 쪼갤 수 없는 위상 공간이.
완전 그래프
이론에서 완전 그래프(完全graph)는 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프이.
완전 이분 그래프
이론에서 완전 이분 그래프(完全二分graph)란 꼭짓점의 집합이 서로 겹치지 않는 두 집합 X와 Y의 합집합이고 X의 모든 꼭짓점이 Y의 각각의 꼭짓점과 하나의 변으로 연결되어 있는 이분 그래프이.
P (복잡도)
P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이.
참고하세요
그래프 이론의 계산 문제
다항 시간 문제
- 벨먼-포드 알고리즘
- 부합 (그래프 이론)
- 최단 경로 문제
- 최장 공통 부분 수열
- 플로이드-워셜 알고리즘
조합 최적화
또한 부합 (그래프), 최대 매칭로 알려져 있다.