제레미 베러미의 타임라인

완전그래프 위 그림과 같이 모든 정점 사이에 모서리를 갖는 그래프를 완전그래프라고 한다. 한마디로 모든 Vertex가 서로 연결되어 있다고 보면 된다. 이 경우 n(n-1)/2 가 모서리의 개수가 된다. 싸이클 그래프 위 그림처럼 가장자리끼리만 모서리로 연결된 그래프를 Cycle 그래프라고 한다. n이 모서리의 개수가 된다. 휠 그래프 위 그림처럼 도형 가운데에 정점이 하나 들어가서 각 정점을 잇는 형태의 그래프다. 이 경우 모서리의 개수는 n*2가 된다. N-CUBE 그래프 다차원적으로 복잡한 관계를 컴퓨터에게 전달해야 할 때 각 정점에 규칙을 부여할 필요가 있다. Q1, Q2, Q3은 각각 1차원~3차원의 그래프를 나타낸 것이다. 얼핏 복잡해보이지만 알고보면 쉽다. [Q1 그래프] 정점이 2개로, 0..

그래프 이론은 객체 간의 관계를 모델링하기 위해 사용하는 이론이다. 소셜 네트워크 관계망, 네비게이션 서비스 등등 다양한 분야에서 사용되고 있다고 한다. 먼저 간단한 용어 정리부터. Vertex : 정점 Edge : 연결선 정점과 연결선을 잇는 형태로 그래프가 만들어진다고 보면 된다. [다양한 그래프의 종류] 1. 단순 그래프 (Simple Graph) 2. 멀티 그래프 (Multi Graph) 3. 의사 그래프 (Pseudograph) 4. 방향 그래프 (Directed Graph) / 무방향 그래프 (Undirected Graph) 앞서 그래프들의 특징을 정리하면 다음과 같다. Simple Directed Graph, Directed multigraph 가 생소해보일 수 있는데 영어 뜻을 생각해보면 ..

행렬의 계수(RANK)는 행 전체가 0이 아닌 행의 개수를 의미한다. 그냥 쉽게 생각해서, '행렬의 계수 = 피벗의 개수' 이다. 바로 예제를 보면서 이해해보자. 위 4개의 행렬 모두 가우스 소거를 통해 피벗이 정해졌다. 이때 RANK는 행 전체가 0이 아닌 행의 개수이므로, (1) 4, (2) 2, (3) 3, (4) 3 가 정답이 된다. 쉬운 개념. RANK를 구할때 잡기술이라고 한다면, 'RANK를 구할때에는 어떤 행에 실수배를 임의로 해도 된다' 는 것이다. (물론 몰라도 문제 풀땐 지장이 없음) '행렬식'을 구할땐 불가능하지만, RANK를 구할땐 '행 전체가 0이 아닌 행'의 개수만 알아내면 되기 때문. RANK를 구할때에는 그냥 어떤 행에 실수배 해버린다음 더하고 빼고 해도 상관이 없다.

가우스 (조던) 소거법은 행렬을 최대한 단순히 하는 과정이다. 이름에 '소거' 라는 키워드가 들어가는 것과 같이, 분수를 약분하듯이 행렬 요소들의 값을 줄여나가는게 특징이다. 가우스 소거법을 사용하는 과정에서는 기본 행 연산을 하게 된다. 이전 포스팅 (링크) 에서 행렬법칙을 간단히 소개했었는데, 기본 행 연산 역시 행렬법칙에서 말한 것과 같은 내용이다. 이렇게 기본 행 연산을 사용하면 선형방정식을 풀거나 행렬을 다루는 등 여러가지 응용에 있어 문제 해결을 더 쉽게 만들어준다고 한다. 기본 행 연산의 과정을 한번 보도록 하자. 기본 행 연산의 목적은 특정 행의 값을 0이나 1의 값으로 바꾸는 것이다. 위 그림처럼 소거를 진행함에 따라 0과 1의 값으로 변해가는 과정을 볼 수 있다. 이렇게 단순화한 행렬은..

1. 역행렬이란? 행렬 A에 어떤 수를 곱해 항등행렬로 만들 수 있는 행렬 B가 있다면, 행렬 A는 '가역적'이라고 하며 행렬 B를 행렬 A의 '역행렬'이라고 한다. 여기서 잠깐, 항등행렬이 뭐였더라? 더보기 위 그림과 같이 대각행렬이면서 대각항이 모두 1인 행렬을 항등행렬이라고 한다. (이전 포스팅 6번 항목 참고) 보다 정확한 정의는 다음과 같다. 2. 역행렬을 구하는 방법 역행렬을 구하는 방법은 다양하다. (1) 가우스-조단의 방법 (2) 한 행렬을 변수로 놓고 곱을 구해서 항등행렬이 되도록 하는 방법 (3) 수반행렬을 이용하여 구하는 방법 오늘은 이 중에서 (3)에 해당하는 방법, 수반행렬을 이용해 역행렬을 구하는 방법을 알아보도록 하겠다. 3. 수반행렬이란? '행렬 A에 대한 여인수를 성분으로 ..

1. 3*3 행렬식을 구하는 방법 - 소행렬 이용 : 그냥 저대로 따라하면 3*3 행렬식을 구할 수 있다. "아니 그런데, 이해도 되지 않는걸 그냥 달달 외우라고?" 어떻게 저런 식이 나오게 되었는지 원리를 알면 더 쉽게 외울 수 있다. 천천히 알아보도록 하자. 1) 하나의 행 또는 열을 훑는다. : 행을 훑든 열을 훑든 상관없다. 위 그림에서는 행을 훑은 모습이다. (첫번째 행) 2) 소행렬을 곱해준다. (마이너 매트릭스) : 행렬들에 소행렬 M을 곱한다. "소행렬? 마이너매트릭스? 그게 뭔데... 처음보는 용어가 나왔다고 당황하지 말자. 소행렬은 'i행과 j열을 제외한 나머지 성분'으로 만들어진 행렬이다. 예를들어, a11 이라는 행렬의 소행렬은 1행과 1열을 제외한 나머지 행렬을 의미한다. 그림으로..

1. 행렬식? 행렬식(Determinant)이란 정방행렬에 스칼라 값(수)로 대응시키는 특별한 함수다. 교수님은 그냥 '숫자에 대한 컴포넌트들을 가지고 의미있는 개념을 만들어내기 위한 식' 으로 이해하면 된다고 한다. 2. 행렬식의 법칙 행렬 A에 대한 행렬식은 Det(A) 와 같이 표현한다. 또한, 2x2 행렬에서 행렬식의 값은 a*d - b*c = (행렬식의 값)이다. * 3x3 이상의 행렬은 구하는 방법이 복잡하니 나중에 다루려 한다. 행렬식에는 4가지 정도의 특징이 있는데, 바로 다음과 같다. 1) 하나의 행 또는 열의 공통인수는 밖으로 뽑아낼 수 있다. : 행이나 열이 공통 인수를 가지고 있다면 밖으로 뽑을 수 있다. 예를 들어, 위 그림에서 첫번째 행렬 중 첫번째 행은 [2, 4] 값을 가지고..

1. 행렬 법칙 - 덧셈, 스칼라 곱 지난 포스팅에서 다룬 행렬의 덧셈과 뺄셈, 스칼라 곱 연산에 이어지는 내용이다. 어디까지나 최대한 간단히 행렬의 개념을 다루는 포스팅이기 때문에 증명은 다루지 않겠다. (이후의 대학 수업에서 증명을 배우게 된다면 그때 추가적으로 포스팅해보려 한다) 2. 행렬 법칙 - 곱셈 여기서 주의할 점은, 행렬의 곱 연산에서 '교환법칙은 성립하지 않는다'는 것이다. 결합법칙이나 배분법칙은 행렬의 덧셈에서와 같이 똑같이 성립한다. 3. 행렬의 거듭제곱 행렬의 거듭제곱 역시 어려울 것 없다. A의 세제곱은 A*A*A 연산과 같고, 이전에 배운 행렬의 곱셈을 이용해 계산하면 끝. 여기서 [A의 n승] 행렬은, 모든 행렬 요소가 [2의 n-1승]인 행렬이라는 성질을 이용하면 더 편리하게..

1. 행렬이란? 행렬(Matrix)는 수 또는 문자를 배열의 형태로 나타내는 것을 말한다. 2. 행렬의 크기 행렬의 가로줄은 행(Row), 세로줄은 열(Column)으로 읽는다. 프로그래밍을 할 때에도 많이 쓰이는 영단어이니 확실히 익혀두도록 하자. 만약 햇갈린다면 다음과 같은 방법을 사용해보자. 행렬은 행과 열로 이루어져 있으며, 크기를 나타날때 [행X열] 로 표현한다. 다음과 같은 행렬을 보자. 가로줄(행)이 2개, 세로줄(열)이 3개이니 위 행렬은 2x3 행렬이다. 읽는 방법은 "2행 3열", 또는 "two by three" 행렬이라고 읽어주면 된다. 3. 정방행렬 정방행렬(Square Matrix)는 행과 열의 개수가 같은 행렬을 의미한다. 쉽게 말해 다음과 같은 행렬을 생각하면 된다. 4. 행렬..