00:20 인접행렬 (adjacent matrix) 그래프를 행렬로 표현한 것 그래프는 인간의 눈으로 보기에 가시성이 좋지만, 컴퓨터(계산기)에게는 불편함 따라서 그래프를 행렬로 바꾸는 작업이 필요하고, 그래프를 행렬로 바꾼경우 '인접행렬'이라고 부른다 01:19 인접행렬 만드는 법 꼭지점(Node)끼리 연결된경우 1*, 연결안된경우 0 대각성분은 0임** * 꼭지점(Node)간 변(Edge)이 2개면 2임 **루프를 제외, 루프인경우 루프1개마다 1씩 증가 03:05 인접행렬 특징 행렬의 모든성분의 합 = 변의개수(e)의 2배 = 전체그래프의 차수의 합(Σｄ) 04:28 인접행렬의 계산기를 통한 계산할 수 있는 것 M^2의 성분들이 의미하는 것 = 길이2인 경로의 개수 * 특히 대각성분은 회로의 개수임 M^3의 성분들이 의미하는 것 = 길이3인 경로의 개수 * 특히 대각성분은 회로의 개수임 1) 경로의 수 ex. B→E인 길이2인 경로의 수 인접행렬(M)의 B행 x인접행렬(M)의 E열 = M^2의 B행 E열 성분 11:05 2) 회로의 수 인접행렬의 대각성분은 경로의 개수임 3) 삼각형의 수 예제의 경우 무지향성 그래프를 상정하였으므로, 삼각형의 수는 대각성분/2 해야함 (ABDA나 ADBA를 같은 회로로 보는 것)
![[고급수학]다양한 그래프(오일러,해밀턴,수형도)](http://i.ytimg.com/vi/uO_FrT14o7g/mqdefault.jpg)
00:20 인접행렬 (adjacent matrix)
그래프를 행렬로 표현한 것
그래프는 인간의 눈으로 보기에 가시성이 좋지만, 컴퓨터(계산기)에게는 불편함
따라서 그래프를 행렬로 바꾸는 작업이 필요하고, 그래프를 행렬로 바꾼경우 '인접행렬'이라고 부른다
01:19 인접행렬 만드는 법
꼭지점(Node)끼리 연결된경우 1*, 연결안된경우 0
대각성분은 0임**
* 꼭지점(Node)간 변(Edge)이 2개면 2임
**루프를 제외, 루프인경우 루프1개마다 1씩 증가
03:05 인접행렬 특징
행렬의 모든성분의 합 = 변의개수(e)의 2배 = 전체그래프의 차수의 합(Σｄ)
04:28 인접행렬의 계산기를 통한 계산할 수 있는 것
M^2의 성분들이 의미하는 것 = 길이2인 경로의 개수 * 특히 대각성분은 회로의 개수임
M^3의 성분들이 의미하는 것 = 길이3인 경로의 개수 * 특히 대각성분은 회로의 개수임
1) 경로의 수
ex. B→E인 길이2인 경로의 수
인접행렬(M)의 B행 x인접행렬(M)의 E열 = M^2의 B행 E열 성분
11:05
2) 회로의 수
인접행렬의 대각성분은 경로의 개수임
3) 삼각형의 수
예제의 경우 무지향성 그래프를 상정하였으므로, 삼각형의 수는 대각성분/2 해야함 (ABDA나 ADBA를 같은 회로로 보는 것)
과학고 재학중인 1학년 학생입니다. 저희의 연구 주제와 밀접한 관련이 있어 연구 보고서에 화면캡쳐본을 삽입하려 하는데 괜찮을까요?