알고리즘 공부방

gazelle-and-cs.tistory.com/10 en.wikipedia.org/wiki/Hall%27s_marriage_theorem 이분그래프 $G=(L+R, E)$에서, $L$의 부분집합 $S$에 대해 이와 연결된 $R$의 부분집합을 $N(S)$라 하자. 이 이분그래프에서 L의 모든 정점이 참여하는 매칭이 존재할 필요충분조건은 모든 $S$에 대하여 $|S| \leq |N(S)|$ 가 성립하는 것이다.

1. Walk Sequence of vertices and edges of a graph. Vertex can be repeated. Edges can be repeated. Open Walk : starting vertex != ending vertex Closed Walk : starting vertex == ending vertex 2. Trail Open walk in which no edge is repeated. Vertex can be repeated. Edges cannot be repeated. 3. Circuit Closed walk in which no edge is repeated. Closed trail. Vertex can be repeated. Edges cannot be re..