Major Study

신장트리(Spanning Tree) 그래프 G의 모든 꼭짓점을 노드로 포함하는 트리 T 최소신장트리(Minimal Spanning Tree) 그래프 G의 모든 꼭짓점을 노드로 포함하면서 노드 간의 비용을 최소로 하는 트리 T 최소신장트리를 유도하기 위해 프림 알고리즘이나 크루스칼 알고리즘을 활용함. 1.프림 알고리즘(Prim Algorithm) (1)모든 변들 중 가중치가 가장 작은 변을 선택함. (2)가중치가 작은쪽으로 변을 계속 이어나감 (3)순환이 형성되는 경우 그 변은 선택하지 않는다. 예제이런 그래프가 있다고 하면 프림 알고리즘의 순서는이렇게 된다. 가중치가 작은 edge부터 이어가서 계속 작은 쪽으로 이어가면 결국 노드간의 비용이 가장 작아지는 트리가 나온다. 2.크루스칼 알고리즘(Kruska..

트리(Tree) 루트라는 특별한 노드를 갖고 그래프를 구성하는 단순경로가 존재하는 비순환의 연결그래프 노드(Node) 트리인 그래프 T를 구성하는 꼭짓점 루트(Root) 트리인 그래프 T의 가장 높은 곳에 위치하는 시작노트 ->A 부모 노드(Parent Node) 임의의 노드의 한 단계 상위 노드 자식 노드(Child Node) 임의의 노드의 한 단계 하위 노드 형제 노드(Sibling Node) 임의의 노드와 부모가 같은 노드 리프 노드(Leaf Node) 자식 노드가 없는 노드 중간 노드(Internal Node) 루트 노드나 리프 노드가 아닌 노드 조상 노드(Ancestor Node) 임의의 한 노드에 이르는 경로에 포함된 모든 노드들 자손 노드(Descendant Node) 임의의 한 노드에서 리..

그래프의 차수(Degree) 꼭짓점 v에 근접하는 모서리의 수 이 그래프에서 꼭짓점 1의 차수는 1, 2의 차수는 3이다. 차수에대한 정리 1. 그래프G=(V,E)에서 모든 꼭짓점의 차수의 합은 모서리의 수의 두배이다. 위 그래프도 모서리의 수는 2이고 꼭짓점의 차수의 합은 4이다. 2. 그래프 G=(V,E) 에서 차수가 홀수이면 꼭짓점의 수는 짝수이다.(아니면 그래프가 아님) 부분그래프와 부분신장 그래프 부분 그래프 : 어떤 그래프 G에 포함되는 일부 꼭짓점과 모서리로만 그린 그래프 부분신장 그래프 : 부분 그래프 중에서 그래프 G의 꼭짓점을 모두 포함하지만 모서리는 일부만 포함하는 그래프 차례대로 그래프 G, 부분그래프, 부분신장 그래프이다. 부분그래프는 그래프 G에 속해있으면 되고, 부분신장 그래프..

이번 글에서는 함수에 대해서 알아 볼 것이다. 목차는 함수의 개념, 함수의 종류, 합성함수, 함수의 특성에 대해서이다. 함수의 개념 함수(Function : A->B) 집합 A,B에 대해 집합 A에서 B로 가는 관계가 성립할 때, 집합 A의 원소 a에 대해 집합 B의 원소 b 하나가 대응되는 관계 즉, 하나의 입력값에서 하나의 출력값이 나와야한다. 그림으로 보자면 이렇게 f(a)=1, f(a)=2가 나오면 안된다. 오직 하나의 출력값만이 나와야한다. 단사함수(injective function)쉽게 말하자면, 정의역의 원소들이 공변역의 원소들이랑 한놈씩 대응하는 함수이다.이런 함수가 단사함수이다.이것도 단사함수이다. 근데 공변역에 원소가 더 많으면 인기없는 원소들은 정의역한테 선택을 못받을 수도 있음… 전..

저번 포스팅에 이어서, 이번에는 합성관계, 합성관계의 거듭제곱, 추이관계와 거듭제곱의 관계, 폐포, 연결관계와 추이관계에 대해서 알아볼 것이다. 1.합성관계(composition Relation) 이걸 그림으로 표현하면이렇게 된다. 뒤에 있는 관계가 먼저이기 때문에 관계행렬로 표현할 시 관계R이먼저 오게 된다. 2.합성관계의 거듭제곱 관계행렬로 나타내었을 때, R의 2승은 자기자신을 부울곱 해주면 된다. 거듭제곱과 추이관계에는 관계가 있는데 그 관계는이것이다. 말로 하면 어려우니까 예제를 들어보자면이렇게 할 수 있다. 이걸 또 증명해보자. 우선 관계R이 추이관계인지 알아봐야겠다.그 후 추이관계와 거듭제곱의 관계를 이용해서 풀어보면이렇게 된다. 3.폐포(Closure) 집합 A에 대한 관계를 R이라 하고,..

오늘은 이산수학 중 관계(Relation)에 대해서 할 것이다. 먼저 기본용어인 정의역,공변역,치역,역관계에대해서 알아보고 그 후 관계의 표현 방법에 대해서 알아볼 것이다. 1. 정의역(Domain : dom(R))2. 공변역 (Coomain : codom(R)) 3. 치역(Range : ran(R)) 4.역관계(Inverse Relation : R^-1) 아마 이렇게 글로만 봤을 때는 이해가 안될것이다. 근데 예제를 풀면 아주 쉽게 이해할 수 있다. 문제를 풀어보자면, 정의역=dom(R)=A={a,b,c,d} 공변역=codom(R)=B={p,q,r} 치역=ran(R)={p,r} 이다. 치역은 두번째 원소에서 R에 포함되지 않은 원소는 빼주면 된다. 이제 이러한 관계들을 표현하는 방법들을 알아보겠다. 총..