이산수학 6주차

자 그 다음에

어디서 시작했냐 이렇게 시작을 했다고 합니다. 예전에 오일러라는 사람이 산책을 하면서 이렇게 흥인 형태의 다리를 건너가려고 하는데 갑자기 드는 생각이 어디서 출발하든 모든 다리를 한 번씩 지나서 갈 수 있는 방법이 있겠느냐 이런 걸 생각을 하면서 그래픔 라는 개념을 처음에 도입을 했다고 합니다. 출발하는 지점에 상관없이 어떤 다리를 한 번씩만 지나서 갈 수 있는 모든 다리를 지나갈 수 있는 경로가 있겠느냐 이런 방법이 있겠느냐 이런 걸 볼까 찾기 시작해서 당연히 이런 걸 볼까 그래프 이론이다 하는데 당연히 이거를 다리를 직접 건너는게 아니라 이거를 그림으로 통해서 하면 훨씬 더 효과적으로 우리가 일일이 건너 보지 않아도 알 수 있지 않겠냐 라고 생각을 해서 만든게 그래프 이론이다 라고 볼 수가 있어요 그림 그려보면 어디갔지? 아 요렇게 요렇게 그래서 요런 다리를 이런 그림 형태로 바꿔서 생각을 해보자 그래서 각각의 지점과 연결된 다리를 점과 선으로 바꿔서 이와 같이 바꾸면 우리가 이제 다리를 건너지 않고도 이 그림을 통해서 일과 같이 손으로 확인하는 방법으로 구할 수 있다는 게 그래프 이론이라는 형태에 대한 이야기를 이야기해볼 수가 있어서 이렇게 시작을 했다 그래서 이런게 그래프 이론이다 라고 우리가 이야기 해볼 수가 있어요 그래서 시작은 이런 데서 출발했다 그래서 다양한 분야에 쓰인다 통신 네트워크 이런 알고리즘 탐색 이런 분야에 다양하게 쓰인다 라고 이야기 해볼 수 있겠죠 이런 지도도 우리가 그래프 이론 중에 하나의 활용법이다 그래프라는 건 뭐냐 여러분이 알고는 1차원스 그래프, 2차원스 그래프 이런 게 아니라 여기와 같은 점들이죠 여기서 점을 버텍스라고 하고 정점 그래서 얘네 점들을 모아놓은 집합을 대문자 V 그 다음에 선들을 모아놓은 집합을 선은 엣지라고 해서 대문자 E 그래서 그래프라는 건 점과 선을 모아놓은 집합이다 그래서 얘네들을 우리가 그래프라고 이런 도로입니다 그래서 일반적인 그래프는 전과 선을 모아놓은 형태로 우리가 그래프라는 형태로 이름을 붙이자 어떤 점과 어떤 점을 연결하는 선 이런 형태로 이야기하자 점과 점들을 여러가지 점들을 이하와 같이 있는 형태를 그래프다 라고 이야기해볼 수 있겠죠 그래프 라고 하자 그 다음에 그래프 중에 여러분이 A에서 출발해서 B로 가듯이 화살표가 있는 것을 우리가 방향이 있는 그래프다 라고 해서 방향 그래프 그 다음에 방향이 없는 걸 말 그대로 방향 없는 그래프죠 그래서 크게 두 가지로 나누고 당연히 우리가 알다시피 이제 이런 건 여러분들이 이제 우리가 자칫 다예요 여러분이 알고 있는 이런 거 많이 쓰죠 소위 말하는 벡터 이런 거 같이 이제 1,2다 방향이 있는 그래프 이런 거 많이 쓰죠 우리가 일반적으로 이야기하는 이런 분야에서도 많이 사용한다고 볼 수가 있겠죠 방향이 없는 그래프는 여러분이 저번에 할 때 하세도표 마찬가지로 이런 거 했었죠 그래서 유리수 이런 거 방향이 없는 그래프다 이런 거 마찬가지로 했었습니다 그래서 여러분들이 이와 같이 표현이 가능하지 않겠냐 라고 볼 수가 있어서 두 가지로 크게 나타내보자 해서 이와 같이 이와 같이 점이 4개죠. 1,2,3,4번이라고 불리는 점이 4개랑 그 다음에 얘는 방향이 없죠. 선만 연결돼 있어서 1번과 2번이 연결돼 있다. 2번과 4번 2번과 3번이 연결돼 있다는 걸 이와 같이 표현한 거예요. 그래서 1번, 2번 연결돼 있고 2,3, 2,4 연결돼 있다는 걸 이와 같이 표현해보고 따라서 이런 상태에서 뭐가 존재한다? 아 1번이라는 점에서 출발해서 2번을 거쳐서 3번을 갈 수 있고 마찬가지로 1번, 2번, 4번을 갈 수 있다. 이런 뭐다? 경로가 생기더라. 우리가 뭐죠? 출발하는 지점이랑 도착하는 지점이 각각 존재하는 이런 경로라는 용어가 생기더라. 그래서 1번에서 출발해서 2번을 거쳐서 3번을 가고 이런 식으로 우리가 경로를 생각을 할 수가 있다. 그래서 뭐다? 몇 번에 거쳐서 가느냐. 그래서 1번에 거쳐서 2번, 2번, 3번 가기 때문에 1번, 2번에 거쳐서 3번을 가기 때문에 1번에서 3번으로 가는 경로의 값은 뭐다? 이다. 라고 우리가 이와 같이 경로의 길이라고 불리우는 이런 걸 우리가 생각을 할 수가 있어서 여러분들이 이제 저기 나오는 경로의 길이라고 하는데 어떤 사람은 이거는 값이라고도 하기도 하고 어떤은 크기라고도 이야기합니다. 그래서 경로라는 걸 사람마다 값이라고도 부르기도 하고 크기라도 부르기도 하기 때문에 이거는 용어의 차이예요. 어떤 용어를 좋아하느냐 그 차이로 뿐이지 아가진이의 길을 하고 있다. 워낙 몇 번을 거쳐서 내가 원하는 도착지에 갈 수 있느냐. 그 횟수를 우리가 경로의 길이, 경로의 크기, 또는 경로의 값이다. 등등등 여러가지 이름으로 부르게 됩니다. 그래서 여러분들이 이런 걸 우리가 경로다라고 이름을 부르죠. 경로는 일반적으로 우리가 이제 경로를... 여기 나와있는 경로라고 있죠. 경로는 일반적으로 출발하는 점이죠. 출발점이랑 마찬가지로 도착점이 같지 않아도 돼요. 일반적으로. 이건 경로라고 하고요. 저기 나와있는 사이클이죠. 사이클은 말 그대로 영어죠. 영어인데 이거는 출발점이다 그 점이 다 도착점이 같은 경우를 우리가 싸이클 이라고 이야기합니다 가장 간단하게 이야기 해보면 이어 같이 된다고 어려운 용어를 쓸 필요도 없고 우리가 이제 모자 출발하는 지점과 도착한 지점을 우리가 같으면 사이클 다르면 일반적으로 폭로다 그래서 얘네가 출발점과 도착점이 같으면 사이클 경로중에 일반적으로 일반적인 경우죠. 같은 경우도 있습니다. 출발점과 도착점이 같으면 사이클이고 그렇지 않으면 일반적으로 경로다라고 생각을 하면 되기 때문에 좀 더 얘가 일반적인 상태다 라고 우리가 이야기할 수가 있어서 여러분들이 이어갔습니다. 경로냐? 사이클. 마찬가지로 사이클이라고 하는데 이건 어떤 책은 무슨 해? 순환 등등등 용어로 부르겠습니다. 같은 용어에서 여러분들이 이제 다른 책에 보면 이렇게 쓰기도 하는데 우리는 용어를 하나로 통일하기 위해서 사이클이란 용어 하나만 쓰도록 하겠습니다. 한가지 용어만 활용을 해서 사이클이라고 부르겠다 라고 할 수가 있어요. 앞으로는 그냥 여러개 부를 필요없이 그냥 사이클 하나만 용어를 부르겠습니다. 사이클이다. 이렇게 되겠고 이런 경로에는 크게 두가지가 있습니다. 이거를 좀 있다가 이야기하고 그 다음에 이와 같이 방향이 있는 그래프죠. 여러분 여기 아크라는 용어는 굳이 몰라도 상관없어요. 이건 마찬가지로 아크 선행자, 후속자 이런 거는 뭐 크게 알 필요는 없습니다 선행자는 우리가 알다시피 좀 더 익숙한 용어가 출발점 후속자는 우리가 알다시피 도착점이라는 용어로 쓰면 좀 더 익숙한 용어가 되기 때문에 이거는 사실상 영어를 어떻게 번역하느냐에 따라 다르기 때문에 어떤 사람은 선행자라고 부르고 어떤 사람은 시발점이라고 보고 어떤 사람은 출발점이라고 부르기 때문에 사실상 이거는 큰 차이는 없고 우리가 좀 더 익숙한 용어로 우리가 출발자 도착점 하면 되죠 그래서 여러분들이 다 어차피 이것도 우리가 같은 비싼 뜻을 갖기 때문에 마찬가지로 라크 이런 거 용어 몰라서 상관없어요 여러분들이 이제 필요한 용어만 기억을 하자 자 그래서 마찬가지로 1번에서 출발해서 4번으로 간다 라고 했을 때 하나 둘 셋 가면은 2번은 하나 둘 세 번의 경로를 거쳐서 가기 때문에 경로가 가장 큰 것은 이렇게 한 칸, 두 칸, 세 칸은 이 경우가 경로가 3이 되겠고 그 다음에 경로가 값이 제일 작은 건 이렇게 한 번에 가는 거죠 따라서 이렇게 가면 경로가 1, 이렇게 가면 경로가 3, 그 다음 마찬가지로 이렇게 가면 경로가 2다 경로의 값을 구할 수가 있지 않겠냐는 그런 걸 우리가 경로의 각, 경로의 크기다 라고 이름을 부릅니다. 어려운 계산은 아니에요. 몇 번 지나가느냐 보고만 확인하면 되죠. 그 다음에 이런 그래프 중에는 트리라는 것도 있다. 이런 걸 알다시피 맨 위가 루트죠. 소위 말하는 우리가 이야기하는 뿌리 근이라고 이야기하죠. 뿌리에서 출발해서 밑에 방향으로만 이렇게 진행되는 걸 우리 트리부저라고 하는데 이거는 중간고사 이후에 뒷부분에 나오기 때문에 그때 가서 좀 더 자세히 알아보기로 하고 트리는 그때 또 나옵니다. 그래서 여러분들이 여러가지 됐고 일반적으로 여러분들이나 주로 다루는 게 뭐다 가지죠 가지가 두 개씩 버든 이진 트리를 우리가 주로 이야기하고 트리는 마찬가지로 이 화살표를 거의 없앤 다음에 우리가 이야기를 하죠 이 때문에 여러분들이 이런 것도 있다 그래서 얘는 뿌리라고 불리는 하나의 정점이 있다는 거 여기서 출발한다 라는 이런 구조를 우리가 트리라고 이야기하자 이런 동어는 나중에 또 나오니까 그때 가서 자세하게 설명을 하고 마찬가지로 그래프의 용어에 대해서 설명을 하는데 이와 같이 뭐다? 점과 점을 연결하는 선이 하나만 있는 걸 뭐라고 그런가? 싱글이죠. 심플 또는 싱글 뭐 이렇게 부르긴 합니다. 왜냐하면 선이 하나이기 때문에 단순하다라고 해서 단순 그래프다 라고 이야기합니다. 점과 점을 연결하는 선이 하나씩만 존재할 때 이거 단순 그래프 그 다음에 그렇지 않을 때죠 그래서 전과 전을 연결하는 선이 여러 개 있는 것을 우리가 멀티 또는 다중이죠 우리가 다 많을 다 그래서 다중 그래프 또는 영어로 그냥 멀티 그래프 좀 바꾸자면 다중 그래프죠 여러분들이 이와 같이 전과 전을 연결하는 여러 개의 선이 연결되어 있을 때 이런 걸 우리가 멀티 그래프 또는 다중 그래프다 라고 이루어져서 기본적인 용어들에 대해서만 설명을 하고 있어요. 이런 걸 많이 쓴다. 그 다음에 이제 뭐 맞죠? 그 다음에 마찬가지로 이와 같이 여기처럼 정과 점을 연결해 얘랑 얘랑 선으로 연결되어 있다. 얘랑 얘랑 인접해 있다. 또는 연접해 있다. 이런 여러가지 용어를 부릅니다. 그래서 정과 점은 선으로 연결되어 있다. 또는 접해 있다. 연접해 있다. 인접해 있다. 이런 몇가지 용어들을 같이 씁니다. 그래서 여러분들이 보면 마찬가지로 부르는 사람에 따라 조금씩 다를 것 뿐이지 뭐다 정과 점이 선으로 연결되어 있다. 라는 의미를 우리가 이와 같이 이야기 해볼 수 있겠고 그래서 마찬가지로 이와 같이 대기. 그 다음에 우리가 어떤 용어를 쓰냐 이런 용어를 써요. 정점의 차수라고 합니다. 그래서 정점의 차수,'글'이라고 하는데 이건 뭐냐면 이건 뭐냐면 정점의 차수는 뭐다? 점에 연결된 선의 개수를 우리가 정점의 차수라고 합니다. 그래서 여러분들이 정점 C의 차수는 하나 둘 셋 네개죠. 여기서 4 마찬가지로 차수는 하나 둘 셋 넷 다섯 여섯 개죠. 마찬가지로 B의 차수는 선이 몇 개냐. 하나 둘 셋 넷 개죠. 4 마찬가지로 B의 차수는 여기도 마찬가지로 하나 둘 셋 넷 다섯 여섯 개다. 이렇게 이제 점에 연결된 선의 개수를 우리가 정점의 차수라고 부릅니다. 그래서 우리가 이런 걸 우리가 계산한다. 이거는 사용을 합니다. 그래서 여러분이 차수라는 개념을 알아두기 바란다 라고 우리가 이와 같이 이야기 해볼 수가 있어요. 그래서 여러분들이 이 정점의 차수를 이용해서 우리가 다음에 어떤 일을 할거에요. 정점의 차수를 기억하자. 그 다음에 마찬가지로 차수의 합. 정점의 차수. 의 합하면 당연히 몇 개죠? 이거 계산하면 당연히 스무 개죠. 그 다음 선의 개수. 선의 개수는 여러분 세보면 3개, 5개, 3개, 5개죠. 총 10개예요. 그래서 선의 개수는 10개입니다. 그래서 10개예요. 보다 정점의 차수는 20개고, 얘는 10개니까 곱하기 2를 하면, 곱하기 2를 하면 핫하지더라. 그래서 여러분들이 이와 같이 뭐다? 정점의 차수의 합은 선의 개수의 정확하게 2배다. 이유는 간단하죠. 이유는 간단합니다. 왜 그러냐면 A랑 B라는 점에 대해서, D죠. 여기서 정점의 개수를 잘 셀 때 이쪽에서 정점의 차수 2개 세고 이쪽에서 정점의 차수 2개가 세기 때문에 같은 선을 2번 세기 때문에 당연히 2배가 나올 수 밖에 없어요. 이와 같이 정점의 차수의 합을 다하면 원래 있던 선에 정확하지 2배의 개수가 나오더라 해서 여러분들이 이와 같이 보다 차수의 합은 선에 두 배다. 라는 이와 같은 형태를 우리가 간단하게 생각을 해볼 수가 있어 어렵지 않은 내용이다. 이와 같이 정점의 차수라는 걸 우리가 앞으로 쓸 거다. 자 그 다음에 마찬가지로 또 그래프에 나오는 용어에 대한 설명으로써 집합이 있으면 부분집합이 있듯이 그래프도 있으면 그림집합이 부분 그래프가 있다는 얘기죠 그래서 여러분들이 뭐다? 그래프 중에 점과 선을 떼어버리면 뭐다? 부분 그래프다 라는 얘기죠 그래서 원래 있던 그래프에서 마찬가지로 이와 같이 얘네들을 없애버리면 이만큼 없애버리면 얘를 없애버리면 이만큼의 그래프가 남는 거죠 따라서 이거는 원래 있던 그래프의 부분이다 그래서 부분 그래프다 라고 우리가 이야기합니다 그래서 여러분들이 부분 집합이랑 다를 게 없어요 그 다음에 여기 나와있는 생성 부분 그래프는 뭐냐 점은 그대로 두고 점은 그대로 두고 선만 없앤거에요 이 선 없애고 이 선 없애고 이 선만 없앤거에요 그럼 뭐다? 얘는 점이 따로 떨어져 있죠 그래서 이와 같이 생긴 걸 부분 생성 그래프라고 하는데 뭐 자주 등장하는 용어는 아니기 때문에 그냥 이 부분 생성 그래프 중 얘는 뭐 그냥 아 이런 것도 있다 라는 정도로 여러분들이 이제 보면 됩니다 그래서 얘가 같이 이제 중요한 개념만 한테에서 여러분이 기억을 해보자 자 그 다음에 경로는 아까 했었죠 자 이런 경로는 크게 두가지로 나온다 그래서 경로는 단순 기본 크게 두가지로 분리합니다 차이점은 있어요 차이점은 뭐냐면 얘는 선 얘는 점이에요 빨간색은 없구나 그래서 안 나오니까 묘와 같이 우리가 이야기 해보세요 단순은 뭐다? 선을 두 번 밟으면 안돼요 선은 한 번, 기본은 점을 한 번 기준이 달라요 단순 경로는 뭐다? 선을 한 번씩만 지나는 경로 기본 경로는 뭐다? 점을 한 번씩만 지나는 경로라고 생각하면 됩니다 기준점이 다르다. 뭘 기준해서 경로를 만드느냐 선을 기준으로 해서 선을 한 번만 지나면 단순 경로 점을 한 번만 지나면 기본 경로다 라고 우리가 이야기합니다 마찬가지로 이와 같이 당연히 사이클도 두 가지가 있겠죠? 이쪽도 단순, 이쪽도 기본이 있겠죠? 사이클도 얘도 마찬가지로 선, 얘도 점 이와 같이 두 가지 기준으로 우리가 사이클을 만들 수가 있더라고요 여러분들이 이와 같이 우리가 보다 경로 중에 선을 기준으로 하면 단순경로 점을 기준으로 하면 기본경로다 그래서 두 개의 차이점이 있다는 거 이렇게 같이 구별을 해서 기억을 해야 됩니다 그래서 뭐가 기준이냐? 라는 거 한 번만 지나가는 거예요 선을 한 번만 지나가면 점을 한 번만 지나가면 그래서 선을 한 번만 지나가면 점은 여러 번 지나가도 상관없어요 이건 점은 무관해요 그다음에 기본으로 가면 점은 한번만 지나가고 선은 두번 세번 지나고 상관없어요 점 기준이냐 선 기준에 따라서 여러분들이 구별을 해서 기억을 해야 됩니다 이와 같이 이야기를 해보자 기준점이 다르다 라는거 이미 이야기 했죠 사이클인데 여기 또는 수뇌라고 되어 있죠 그래서 수뇌라는 용어를 쓰지 말고 그냥 사이클이라는 용어로 통일해서 사용하도록 하겠습니다 수, 수, 수 이런 거 있는데 하나만 용어를 쓰죠. 사이클이라는 용어만 쓰도록 하겠습니다. 그래서 우리는 사이클이라는 용어만 쓰자. 그래서 단순 사이클, 기본 사이클 있죠. 당연히 아까 얘기한 것처럼 단순 사이클은 선기준, 기본 사이클은 정기준이죠. 여러분들이 두 가지를 구별해서 지옥을 하자. 또 마찬가지로 그래프에 대한 용어를 설명하는데 우리가 뭐다? 정점이 연결되어 있는 걸 모든 정점이죠. 하나라도 이렇게 된 건 없다라는 거죠. 이건 연결 그래프가 아니죠. 말 그대로 연결되어 있지 않죠. 그래서 우리가 단순하게 직관적으로 생각을 하면 됩니다. 정 하나하나도 연결되어 있지 않으면 이거는 연결 그래프가 아니다. 점은 연결되어 있어야 된다. 따로 떨어진 점은 없어야 된다. 라는 게 연결 그래프예요. 어려운 내용은 아니고 마찬가지로 강한 연결 그래프는 뭐다. 여러분들이 저저번주 했던 관계 중에 뭐다. 이거는 대칭이죠. 소위 말하는 양쪽 화살표. A에서 B로 갔으면 마찬가지로 B에서 A로 오는 그래프가 있고 방향 그래프가 있어야 된다 요거를 우리가 강한 연결 그래프라고 이야기합니다 그래서 이와 같이 우리가 방향이 있는 거에서만 우리가 강한 연결 그래프다 라고 하기 때문에 일종의 특별한 경우죠 그래서 우리가 일반적으로 그래프고 그 다음에 이제 연결되어 있는 연결 그래프 그 다음에 방향이 있는 건 방향 그래프 이와 같이 이야기하고 그래서 이와 같이 연결이 되어 있는데 양쪽으로 이와 같이 화살표가 있는 강한 연결 그래프다 라고 이와 같이 이야기하는데 용어가 많으니까 여러분들이 일일이 다 기억할 필요는 다 기억할 필요 없고 내가 여러분들한테 기억해라 라는 정도로만 기억을 해도 충분히 다른 형태의 보는데 지장은 없을 거예요 이와 같이 열어 볼 수 있겠고 그 다음에 연결 요소는 우리가 뭐다 요거는 차수라는 걸 쓸 쓰고 얘는 연결 요소는 잘 쓰지 않습니다 해서 여러분들이 요거는 크게 중요한 개념은 아니기 때문에 사수라는 개념은 훨씬 더 활용도가 높은 개념입니다. 그래서 연결 요소는 생량 자 그 다음에 마찰 가지고 이거 연결 그래프죠. 연결 그래프인데 뭐다 화살표가 있고 화살표가 한쪽만 있죠. 그래서 이거 뭐다? 연결 그래프이긴 하지만 화살표가 한쪽밖에 없기 때문에 그냥 연결 그래프죠. 강한 연결 그래프는 아니라 강한 연결이 되려면 왔다 갔다 양쪽 화살표가 있어야 된다. 그 다음에 2번, 얘는 뭐다? 여기가 떨어져 있죠. 여기가 분리되어 있죠. 그렇기 때문에 이쪽이랑 이쪽이랑 분리되어 있기 때문에 얘는 같은 하나의 통체의 또 하나의 그래프인데 왼쪽 오른쪽이 분리되어 있기 때문에 이거는 연결이 되지 않았다. 그래서 이거는 연결 그래프가 아니다. 그래서 만약에 내가 여기다 선을 하나 이렇게 그리면 연결 그래프가 되는 거죠. 그래서 여러분들이 이 경우는 이제 연결 그래프가 아니고 그냥 우리가 일반적으로 그래프다. 라고 우리가 이름을 부를 수가 있더라. 기본적인 용어에 대해서 이런 용어들을 쓴다는 것을 설명하고 있는거죠 자 그 다음에 아까 얘기한 멀티 그리프죠. 이거를 어떻게 보다 한 점에서 출발해서 다리를 한번씩 건너는 경로죠. 소위 말하는 뭐다? 단순 경로에요. 선을 한번씩만 지나는 경로이기 때문에 단순 경로죠. 제자리로 안 돌아와도 돼요. 다리만 한번씩 건너면 되기 때문에 이것보다 단순 경로가 있느냐. 어떤 점에서 출발하든 상관없이 다리를 한 번씩만 지어날 수 있는 경로가 있느냐 점은 몇 번 지나면 상관없고 다리만이죠 얘는 뭐다 다리를 한 번씩만 지내는 거기 때문에 단수 경로가 있느냐 그럼 이걸 어떻게 하면 단수 경로를 만들 수 있겠느냐 라는 걸 보일러나 사람이 해결을 했어요 아 이런 경우만 단수 경로가 존재한다라는 거 방법이 있다 홀수 정점의 차수가 홀수인 게 0개 또는 여기 있는 2개죠 그래서 홀수 정점의 차수가 0개 또는 2개인 경우만 뭐다 모든 다리를 한 번씩만 지나서 건널 수 있는 단순 경로가 존재한다 그럼 뭐죠? 얘를 위로 올라가서 이게 존재하느냐? 이게 단순 경로가 있느냐? 이것이죠. 그래서 정점의 차수가 얼마? 차수는? 3이죠 이것도 3이에요 이것도 3이죠 차수는 이건 5에요 정점의 차수가 홀수인게 몇개? 4개죠 단순경로가 존재하지 않아요 해볼 필요도 없이 어떤 점에서 출발하든 선을 한 번씩 지나서 건널 수 있는 방법은 존재하지 않는다 라는 결론을 얻을 수가 있습니다 그래서 우리가 이와 같은 단순 경로를 오일러라는 사람을 자기 이름을 따서 이걸 오일러 경로다라고 이름을 붙였어요 오일러 경로다 그래서 이와 같이 단순 경로라는 걸 오일러라는 사람이 자기 이름을 따서 오일러 경로를 붙였고 그러면 여기다가 뭐다? 다리를 하나 건설을 해서 뭐다? 오일러 경로를 만들 수 있다 그래서 여기다 다리를 하나 쭉 그리면 얘가 4가 되고 얘가 6이 되니까 뭐다? 홀수인 정점의 차수가 두 개로 줄었죠. 그럼 뭐다? 오일러 경로가 생겨요. 그럼 어디서 출발해야 되냐? 오일러 경로, 즉 뭐다? 선을 한 번씩 경부를 다 지날 수 있는 방법이 존재하는데 어디서 출발해야 되냐? 당연히 여기서 출발하면 안 돼요. 홀스윙 정점에서 출발해야 돼요 만약에 여기서 출발했다 여기서 출발 일로 가죠 일로 갔다가 도착을 해서 내려오죠 일로 갔다가 다시 위로 올라갔다가 내려왔다가 이렇게 가는거죠. 갔다가 이렇게 오면 끝났더라. 여기가 도착점이죠. 그래서 출발을 해서 모든 선을 한 번씩 지나서 그리고 마지막 우리가 안간 다리까지 한 번에 다 지나갈 수 있더라 여러분들이 이와 같이 오일러 경로를 만들어낼 수가 있더라 정점의 차수가 홀수인계 2개만 내면 뭐다? 홀수인 정점에서 출발하거나 하면은 모든 선을 한 번씩 지나서 다른 홀수인 정점의 차수로 도착할 수 있는 이런 오일러 경로가 존재하더라 라고 우리가 이야기해볼 수가 있어 이와 같이 우리가 만들 수 있더라 그럼 당연히 오일러 사이클은 뭐다? 정점의 차수가 0이면 그래서 5, 1, 0 경로랑 그 다음에 사이클이 있죠 그래서 이거는 홀수 차수가 차수가 2개죠 차수가 2개 이건 홀수 차수가 홀수 차수가 이건 0개 요약을 해 볼 수가 있어요 얘는 2개니까 경로죠. 마찬가지로 여기다 선을 하나 더 추가하면 선을 하나 여기다 이렇게 추가하면 4, 4가 돼서 홀스 차수가 아예 없죠. 그렇게 되면 뭐다? 오일러 사이클이 된다. 뭐다? 출발점이랑 도착점이 같아지는 이러한 오일러 사이클을 만들 수가 있어요. 여러분들이 이와 같이 앞에서는 0개 또는 2개라고 했지만 사실상 2개는 오일러 경로 이거는 출발점과 도착점이 다른 거. 오일러 사이클은 출발점과 도착점이 같은 거 이와 같이 우리가 만들어낼 수가 있더라.

여러분들이 이와 같이

오일러는 사람이 이런 거에 해결 방법을 제시했다라고 볼 수가 있어요. 이렇게 우리가 이제 계산할 수가 있더라고요. 이와 같이 오일러 경로와 오일러 사이클 중요한게 뭐다? 선을 한 번씩만 지나는 거예요 그래서 오일러라는 사람이 자기 이름을 짜서 만들었고 그 다음에 우리가 안한게 뭐냐면 점이에요. 점 기준으로 해서 점을 한 번씩만 지나서 경로를 만드는 것. 그거는 이제 뭐다? 뒤에 나와요. 그래서 일단 우리가 지금 한 번 선을 기준으로 선을 한 번씩만 지나는 오히려 경로다라고 우리가 이와 같이 알아볼 수 있겠고 이런 그래프를 우리가 전문적으로 공부하는 분야를 위상기하학이라고 하는 이런 분야가 또 따로 있습니다. 기하학이라는 항문 자체가 원래 뭐냐면 이런 도형이나 그래프를 연구하는 분야가 되겠고 일단 위상이라는 저런 분야는 또 서로의 관계를 연구하는 분야가 되기 때문에 이제 뭐라? 관계랑 도형을 연구하는 항문을 우리가 이상기화각이라고 합니다. 그래서 여러분들이 이거 봤죠. 이거 뭐다? 얘는 논리적 동치다 라고 이야기했죠. 이거죠. 이거. 이거죠. 논리적 동치다 라고 합니다. 그래서 뭐다? 이 그래프랑 이 그래프는 서로 같은 거다. 우리가 일반적으로 선과 선이 만나는 걸 우리가 점이라고 하는데 여기는 점이라고 표시가 되어 있어요 근데 여기는 점이라고 표시가 없죠 이거는 뭐예요? 점이 아니에요 우리가 일반적으로 그래프 이론에서 우리가 이와 같이 점으로 표시된 건 이와 같이 표현이 되어 있고 이거는 점이 아닌 보다 이쪽 선분이랑 이쪽 선분이랑 이렇게 위아래로 지나간다 생각하면 돼요 한쪽은 위로 지나가고 한쪽은 밑으로 지나가기 때문에 이거는 점이 아니에요 그래서 일반적으로 우리가 그래프 이론에서는 점을 이와 같이 찍으면 그게 점이고 찍지 않는 건 그래프에 들어 있던 점이 아닙니다. 그렇기 때문에 이것은 뭐다? 이것을 얘랑 얘랑 논리와 동치다. 여러분이 알다시피 이것을 어떻게 바꿀 수 있냐면 이렇게 바꿀 수가 있죠. 이렇게 이렇게 이렇게 마찬가지로 이렇게 해서 하나는 이렇게 그리고 하나는 이렇게 그리면 되죠. 뭐다? 얘랑 이거랑 같은거고, 이거랑 이렇게 다 세개는 다 같은거죠. 그래서 여러분들이 이와 같이 하면 여기 교차되어 보이는 이런 선을 바깥으로 끄집어내면 이와 같이 되기 때문에 교차되지 않는 형태의 그래프로 만들 수가 있기 때문에 얘네들은 다 논리적 동치인 그래프다 라고 우리가 이야기를 합니다. 그래서 여러분들이 이것보다 교차되는 점이 하나도 없다. 그래서 얘처럼 표차된 점은 원래 표시가 되어 있죠 표시 안 되어 있는 점은 우리가 만나지 않는, 선끼리 만나지 않는 그런 형태를 우리가 표현했다 그래서 여러분들이 얘는 실제 있는 점, 얘는 없는 점이에요 점이라고 하면 안 됩니다 그래서 여러분들이 요새 이렇게 그래프가 논리적 통치다 라는 이와 같이 시국이다 이야기를 해볼 수가 있어요 그래프 이론에서는 점은 반드시 표현을 되어 있다 색칠이 되어 있죠 그렇게 확인하면 됩니다 그래서 이런 그래프를 표현하는 방법은 여러분이 알다시피 뭐가 있다 당연히 그림 그리는 방법이 그것도 뭐가 있다 이와 같이 보다 행렬을 이용해서 표현하는 방법이 있죠. 여러분 저번에 했던 관계 관계에서 관계 행렬을 했었죠. A랑 B랑 관계 있으면 1 관계 없으면 0이죠. 여기서 똑같이 뭐다? 점과 점이 연결되어 있으면 선으로 연결되어 있으면 1 연결되어 있지 않으면 0 이와 같이 5이다. 만든 행렬을 인접 행렬이다. 그래서 점과 점이 인접했다라고 했기 때문에 우리가 뭐다? 이걸 이용해서 인접 행렬이다. 라고 이름을 부릅니다. 점과 점이 연결되어 있으면 1 연결되어 있지 않으면 0으로 표현하는 이러한 행렬을 만들 수가 있다. 마찬가지로 이 행렬을 이용해서 다른 일을 할 수가 있어요. 그거는 뒤에 나와요. 여러분들이 이와 같이 A, B, D죠. A랑 B랑 연결되어 있고 A랑 D 나머지는 연결되어 있는 게 없죠. 자기 자신은 연결이 안 되어 있죠. 마찬가지로 B의 입장에서는 A, B, C, D, C의 입장에서는 C, D, D는 A, B, C가 다 연결되어 있기 때문에 연결되어 있으면, 연결되어 있지 않으면 연결 같은 형태로 우리가 그래프를 표현을 가능하다는 것을 여러분들이 이렇게 우리가 이제 계산해보자 당연히 이렇게 하셔도 되고 마찬가지로 이런 행렬을 보고 그림을 그려보자 당연히 이거는 여러분들이 이제 그림 그리는 거 사람마다 차이가 있죠 그래서 그림을 이렇게 그려도 되고 나는 이렇게 그리자 A B C D 그래서 A, B, C, D, E 이렇게 그려야 돼요 점 찍는 건 사람마다 위치가 다르기 때문에 전혀 상관없습니다 그래서 A랑 C, D 연결되어 있고 B랑 C, D 연결되어 있다 이렇게 해도 우리가 똑같죠 그래서 얘를 돌리면 얘가 나오기 때문에 같은 그림이에요 그래서 점을 나는 여기다가 D로 찍고 여기다가 A로 찍고 싶다 그건 상관없어요 그거는 여러분들이 편하게 정하면 됩니다. 그래서 여러분들이 이제 그거는 정해진 규칙은 없고 여러분들이 마음에 드는 위치에다가 정치고 보면 돼요. 그 다음에 이거는 잘 쓰진 않습니다. 인점 리스트라고 해서 이거는 잘 쓰지 않는데 옛날에 쓰던 거예요. 지금은 잘 안 써요. 이게 왜냐하면 복잡해요. 여러분 알다시피 리스트라는 게 목록이죠. 우리가 굳이 한국으로 바꾸자면 영어가 되기 때문에 리스트라는 단어를 한국으로 바꾸면 목록인데 바로 뭐다? 연결되어 있는 걸 목록화해서 만들었다. 예를 들어 보면 이런 거죠. 여기 보면 1은 4 화살표를 받기만 하지 화살표가 나가는게 없어요. 1은 나가는 화살표가 없다가 여기 점으로 찍어놓은거에요. 2는 이거죠. 1로도 가고 4로도 가죠. 그렇기 때문에 2는 1로 간다. 그 다음에 2는 원래는 4로 간다. 이렇게 써야 되는데 이렇게 해서 4로 간다. 이렇게 써야 되는데 칸을 많이 차지하기 때문에 옆으로 쓴거에요. 그냥 그래서 여러분 마침 이걸 보면은 1에서 출발해서 4로 가는 것처럼 보이지만 1에서 출발해서 4로 가는게 아니라 이거는 2에서 출발해서 4로 가는걸 옆으로 1에서 썼다라고 생각을 하면 됩니다. 그래서 당연히 이걸 이렇게 쓰는 것보다 1은 없다. 2는 1에서 4, 3은 2에서 6 이렇게 쓰는 것도 비슷해요 똑같아요 얘는 그림 그려놓은 거고 얘는 우리가 알다시피 숫자로만 표현한 거죠 3, 5, 6, 이게 목록이죠 소위 말하는 리스트죠 그래서 여러분들이 이렇게 쓰는 방법이 있는데 이거는 예전에 우리가 쓰던 방법이고 그래서 요새는 잘 쓰진 않아요 그래서 이런 것도 있다 라고 그냥 같이 그냥 해볼 수가 있어요 이런 걸 인접 리스트하고 우리가 이야기합니다. 자 그 다음에 아까 했던거죠. 여러분들보다 이와 같이 한점을 출발해서 다른점을 지나서 모든 선을 한번씩 돌아올 수 있는 경로를 보다 단순경로인데 그걸 뭐라고 부릅니다. 오일러 경로라고 이름 붙였죠. 따라하세요 보다 오일러 경로가 된다는 얘기죠. 이와 같이 보다 정점의 차수가 여기가 3이죠. 여기도 3이죠. 정점일차수가 여기도 3, 여기도 3이고 여기는 4죠. 여기는 2 여기는 4죠. 따라서 뭐다? 보일러 경로가 손재하더라. 그래서 어디서 출발한다? 정점일차수가 홀스인에서 출발하는 거죠. 그래서 여기서 출발해서 일로 갔다가 이리로 갔다가 이렇게 한 바퀴 돌아오는거죠 이렇게 가서 이렇게 갔다가 올라갔다가 이렇게 내려오면 우리가 뭐다 출발점은 여기죠 출발점이 여기여서 도착점이 1루가 되는 출발점과 도착점이 다른 이런 오일러 경로를 만들어낼 수가 있다 그래서 모든 선을 한 번씩만 지나서 다 지날 수 있는 이런 경로를 우리가 뭐라고 하는지 오일러 경로라고 본다라고 우리가 이와 같이 이야기 해볼 수가 있겠죠 여러분들이 이와 같이 만들어낼 수 있다면 그럼 오일러 사이클 여기는 순회라고 되어있죠 근데 이거 우리가 용어 하나로 쓰기로 했기 때문에 오일러 사이클이라고 하면 마찬가지로 여기다 뭐다? 오일러 사이클이 안되죠. 오일러 사이클을 만들려면 어떻게 된다? 선만 하나 추가하면 되죠. 여기다 선을 하나 쌓아 그리면 다 닫다가 와서 이렇게 돌아가면 결과적으로 출발점과 도착점이 같아지는 오일러 사이클이 되지 않겠냐 그래서 얘를 두 번이라고 하면 뒤에서 출발해서 한 바퀴를 다 돌아서 제자리로 돌아오는 오일러 사이클을 만들 수가 있더라. 여러분들이 이와 같이 하면 정점의 차수가 다 하나씩 추가되서 여기가 정점이사수 4가 되기 때문에 모일러 사이클이 이와 같이 만들어진다는 거 계산을 수 있겠죠 그래서 이렇게 되는 걸 여러분들이 뭐라고 부른다? 여기 나와있는 한복그리기죠 그래서 여러분들이 알다시피 한복그리기다 라는 개념을 이용한다 선을 한 번에 띄지 않고 한 번에 다 그리는 걸 우리가 한복그리기라고 하는데 이것보다 오히려 사이클을 이야기하는 거예요 여러분들이 오히려 사이클을 한복그리기라는 용어로 우리가 부른다 이거 아까 했던 얘기죠 정점의 차수를 다 합치면 뭐다? 선의 개수의 2배다 아까 얘기한거에요 똑같이 미리 이야기한겁니다 설명이 됐죠 그다음에 마찬가지로 이게 오일러 경로랑 오일러 사이클이에요 정점의 차수가 6이죠 요거는 3 여기도 3 여기는 4 여기도 4죠 여기도 4 정점의 차수가 다 이렇게 되니까 뭐다? 아 이거는 뭐다? 홀스윙이 두개 있으니까 뭐다? 오히려 경로가 있겠죠? 그래서 어디서 출발한다? 얘나 얘 둘중에 하나에서 출발하면 되죠 다른 데서 출발하면 안되고 홀스윙 정점에서 출발하면 됩니다 해보자. 그러면 이쪽에서 출발하면 갔다가 갔다가 갔다가 갔다가 이렇게 와서 왔다가 다시 이렇게 올라갔다가 이렇게 내려왔다가 이렇게 올라갔다가 내려왔다가 이렇게 하면 최종적으로 모든 선을 한 번씩만 지나는 보일러 경로가 존재하지 않겠냐 여러분들이 이와 같이 홀스윈 정점에서 출발해서 홀스윈 정점으로 도착을 하는 보일러 경로 차수가 다 4죠 여기도 4 여기도 4 여기도 4 다 4이기 때문에 사이클이 존재하더라 그래서 얘는 어느정도 출발해도 다 뭐다 한복그리기가 가능하더라 그래서 여기서 출발해서 이리로 갔다가 한바퀴 칼을 아예 겉으로 싹 돈 다음에 갔다가 내려왔다가 갔다가 갔다가 이렇게 하면 이렇게 갔다가 이렇게 갔다가 최종적으로 마지막으로 돌아오면 출발점과 도착점이 같아지는 이런 오일러 사이클을 우리가 만들 수가 있습니다 그래서 여러분들이 이제 정점의 차수가 폴스인지 몇 개냐 그거를 우리가 파악을 하면 이런거 가능하더라 그래서 홀스인 정점차수가 2개면 5위로 격롱 홀스인 정점차수가 0개면 5위로 사이클이 이와 같이 만들어진다는거 이와 같이입니다 확인해볼수가 있다면서 한국그리기가 가능하다 라는게서 이와 같이 보다 연결그래프고 모든 정점차수가 짝수를 가지면 뭐다 한국 글이가 가능하다. 여러분들이 손쉽게 판단을 해볼 수가 있겠죠. 이것도 아무데서나 출발해도 되지 않겠냐 정점을 탈수가 다 4죠. 여기도 4, 4, 4, 4죠. 따라서 뭐다? 아무데서나 출발해도 우리가 이렇게 이렇게 하면 안되죠. 갈 수 있게 찾아야죠. 그렇다고 너무 막가면 안되고 당연히 우리가 이렇게 갔다가 이런 식으로 이렇게 돌아오면 결과적으로 한복그리가 가능하더라. 그래서 여러분들이 어느점에서 출발해도 다 가능합니다. 그래서 확인하는 부분은 어렵지 않더라. 이런걸 보일러 사이클 또는 한국그림이다 라고 이야기합니다 여러분들이 이렇게 파괴해볼 수가 있겠고 다 뭐다? 선 기준이에요 선을 한 번만 지나가는 거예요 선을 두 번 지나가면 안됩니다 점은 여러 번 지나가도 되고 선은 무조건 한 번만 지나간다 이런걸 보일러 경로, 보일러 사이클이다 라고 이야기해볼 수가 있겠고 잠깐 쉬었다가 두 번째 거 진행하도록 하죠 -뭔가 오는 사람 있나요?