예제 1.3 K 5 와 K 3,3 의결합행렬을만들고, 각꼭지점의차수를표시하여라. >> K5 = ones(5,5) - diag(diag(ones(5,5))); degree = sum(k5) degree = 4 4 4 4 4 >> K33 = [zeros(3) ones(3); ones(3) zeros(3)], degree = sum(k33) K33 = 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 degree = 3 3 3 3 3 3

예제 1.4 [ 그림 10-5] 에그려진그래프 G 의결합행렬을만들고, G 의보완적그래프 Gs 의결합행렬을구하여라. >> G = [0 1 1 0 0; 1 0 0 1 0; 1 0 0 0 1; 0 1 0 0 1; 0 0 1 1 0]; >> Gs = ones(size(g)) - G - diag(ones(length(g),1)) % Delete self-loops Gs = 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0

예제 2.3 [ 그림 10-8] 의유향그래프 ( 통신네트워크 ) 에대한결합행렬을구하고유향그래프를그려주는프로그램을작성하여라. [ 그림 10-8 통신네트워크그래프 ]

function prgraph(a, x, y) % prgraph(a, x, y) shows a directed graph % Incidence matrix A of order n with vertex (x(1:n),y(1:n)) % Arrow Consists of 5 points (Zs, Zt, Zn+Nt, Zn-Nt, Zt) % where Zn = 0.9*Zt + 0.1*Zs and Nt is perpendicular to Zt-Zs ArrowX = [1 0 0 0; 0 1 0 0; 0.1 0.9.01 -.01; 0.1 0.9 -.01.01; 0 1 0 0]; ArrowY = [0 0 1 0; 0 0 0 1; -.01.01 0.1 0.9;.01 -.01 0.1 0.9; 0 0 0 1]; n = length(a); if size(a,1) ~= size(a,2) error('incidence matrix A must a square matrix') elseif nargin == 1 x = rand(n,1); y = rand(n,1); elseif nargin ~= 3 error('prgraph(a, x, y) requires A OR A,x,y') elseif length(x)~=n length(y)~=n error('vector x and y must match with the incident matrix A') end newplot; for i = 1:n text(x(i), y(i), sprintf('o %d',i)); for j = 1:n if A(i,j) == 0; continue; end z = [x(i); x(j); y(i); y(j)]; line(arrowx*z, ArrowY*z); end end >> A = [0 1 1 0 1 0; 0 0 1 0 0 0; 0 1 0 1 0 0; 0 0 1 0 1 1; 0 0 1 0 0 1; 0 1 1 1 1 0]; >> x = [0 0 1 2 3 3]; y = [2 0 1 1 2 0]; >> prgraph(a, x, y) o 1 o 5 o 3 o 4 o 2 o 6

예제 2.4 [ 그림 10-8] 유향그래프에서각꼭지점의외차수, 내차수를구하여라. >> A = [0 1 1 0 1 0; 0 0 1 0 0 0; 0 1 0 1 0 0; 0 0 1 0 1 1; 0 0 1 0 0 1; 0 1 1 1 1 0]; >> od = sum(a,2)' od = 3 1 2 3 2 4 >> id = sum(a) id = 0 3 5 2 3 2

예제 2.6 [ 그림 10-8] 과같은네트워크에대해 2- 단계와 3- 단계의수를찾아라. >> A = [0 1 1 0 1 0; 0 0 1 0 0 0; 0 1 0 1 0 0; 0 0 1 0 1 1; 0 0 1 0 0 1; 0 1 1 1 1 0]; >> A2=A^2, A3=A^3 A2= 0 1 2 1 0 1 0 1 0 1 0 0 0 0 2 0 1 1 0 2 2 2 1 1 0 2 1 2 1 0 0 1 3 1 1 2 A3= 0 3 3 3 2 1 0 0 2 0 1 1 0 3 2 3 1 1 0 3 6 3 3 3 0 1 5 1 2 3 0 5 5 5 3 2

예제 2.7 [ 그림 10-8] 과같은네트워크에대해이그래프의 closure 를찾아라 >> A = [0 1 1 0 1 0; 0 0 1 0 0 0; 0 1 0 1 0 0; 0 0 1 0 1 1; 0 0 1 0 0 1; 0 1 1 1 1 0]; >> closure = A^length(A) > 0 closure = 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1

예제 3.2 [ 그림 10-9] 에서보여지는유향그래프에대해서, 다음과같이 (a)a 1 에서 A 9 로 (b)a 9 에서 A 1 로 (c)a 1 에서 A 5 로 (d)a 5 에서 A 9 로 (e)a 9 에서 A 5 로가는단순경로 (simple path) 와그경로의길이를각각찾아라. [ 그림 10-9 구차유향그래프 ] (( 답 )) L(XYZ) 는점 X, Y, Z 를순서대로통과하는경로의길이를표시한다고하자. (a) L(A1A6A9)=2, L(A1A3A6A9)=3, L(A1A3A5A8A6A9)=5. (b) A9 에서 A1 로가는경로는존재하지않는다. (c) L(A1A3A5)=2, L(A1A6A5)=2, L(A1A3A6A5)=3. (d) L(A5A8A6A9)=3. (e) L(A9A6A5)=2, L(A9A8A6A5)=3. 이를일반화하여 Ai 에서 Aj 로가는일정한길이의모든경로를찾는프로그램을작성하고, A1 에서 A9 로가는길이 2 인경로와 5 인경로를모두표시하여라. function findpath(a, path, pos) % findpath(a, path, pos-or-len) with incident matrix A find outs % all possible paths from path(1) to path(end) of fixed length % path(1:pos) = starting to current nodes, path(end) = ending node % path = [path(1) zeros(1,len-1) path(end)] if len>=length(path) % Caution: The output path may visit the same edge more than once if pos>=length(path); path = [path(1) zeros(1,pos-1) path(end)]; pos = 1;

end if pos+1==length(path) if A(path(pos),path(end)) > 0 disp(path); end return end for k = 1:length(A) if A(path(pos),k) > 0 path(pos+1) = k; findpath(a, path, pos+1); end end >> A = [0,0,1,0,0,1,0,0,0; 1,0,1,1,0,0,0,0,0; 0,0,0,0,1,1,0,0,0; 0,1,0,0,0,1,1,0,0; 0,0,0,0,0,0,0,1,0; 0,0,0,0,1,0,1,0,1; 0,0,0,0,0,0,0,0,0; 0,0,0,0,0,1,0,0,0; 0,0,0,0,0,1,1,1,0]; >> findpath(a, [1,9], 2) 1 6 9 >> findpath((a, [1,9], 5) 1 3 5 8 6 9 1 3 6 9 6 9 1 6 5 8 6 9 1 6 9 8 6 9

예제 3.5 유향그래프에서두점사이의경로가존재하는지여부와최단거리를계산하는프로그램을작성하고, [ 그림 10-9] 의각점들사이의거리를구하여라. function Dist = shortpath(a) % shortpath(a) returns minimum path length from Ai to Aj % Dist(i,j) == BigDist means that there is no path from i to j n = length(a); Dist = A; BigDist = Inf; for i = 1:n for j = 1:n if A(i,j) == 0 && i ~= j Dist(i,j) = BigDist; end end end for k = 1:n for i = 1:n for j = 1:n Dist(i,j) = min(dist(i,j), Dist(i,k)+Dist(k,j)); end end end >> A = [0,0,1,0,0,1,0,0,0; 1,0,1,1,0,0,0,0,0; 0,0,0,0,1,1,0,0,0; 0,1,0,0,0,1,1,0,0; 0,0,0,0,0,0,0,1,0; 0,0,0,0,1,0,1,0,1; 0,0,0,0,0,0,0,0,0; 0,0,0,0,0,1,0,0,0; 0,0,0,0,0,1,1,1,0]; > shortpath(a) Dist = 0 Inf 1 Inf 2 1 2 3 2 1 0 1 1 2 2 2 3 3

Inf Inf 0 Inf 1 1 2 2 2 2 1 2 0 2 1 1 3 2 Inf Inf Inf Inf 0 2 3 1 3 Inf Inf Inf Inf 1 0 1 2 1 Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf 2 1 2 0 2 Inf Inf Inf Inf 2 1 1 1 0 예제 3.7 두조직의구조가 [ 그림 10-10] 에서주어진그래프와같다고하자. A 1, A 2, A 4, A 5 와 B 1, B 2, B 6 에대한위치 (status) 를계산하라. [ 그림 10-10 조직내에서의관계를표시하는유향그래프 ]

(( 답 )) 직접적인계산은아래와같다 : S(A1) = 10, S(A2) = 2, S(A4) = 3, S(A5) = 0, S(B1) = 15, S(B2) = 3, S(B6) = 6. >> A = [ 0 1 1 0 0 0 0 0 0; 0 0 0 0 1 1 0 0 0; 0 0 0 0 0 0 1 1 0; 0 0 0 0 0 0 1 1 1; 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0]; >> Dist = shortpath(a), Dist(find(Dist==Inf))=0; Status=sum(Dist,2)' Dist = 0 1 1 Inf 2 2 2 2 Inf Inf 0 Inf Inf 1 1 Inf Inf Inf Inf Inf 0 Inf Inf Inf 1 1 Inf Inf Inf Inf 0 Inf Inf 1 1 1 Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Status = 10 2 2 3 0 0 0 0 0 >> B = [0,1,1,0,0,0,0,0,0; 0,0,0,1,0,0,0,0,0; 0,0,0,0,1,0,0,0,0; 0,0,0,0,0,0,1,0,0; 0,0,0,0,0,0,1,1,1; 0,0,0,0,1,0,0,0,1; 0,0,0,0,0,0,0,0,0; 0,0,0,0,0,0,0,0,0; 0,0,0,0,0,0,0,0,0]; >> Dist = shortpath(b), Dist(find(Dist==Inf))=0; Stauts = sum(dist,2)' Dist = 0 1 1 2 2 Inf 3 3 3 Inf 0 Inf 1 Inf Inf 2 Inf Inf Inf Inf 0 Inf 1 Inf 2 2 2 Inf Inf Inf 0 Inf Inf 1 Inf Inf Inf Inf Inf Inf 0 Inf 1 1 1 Inf Inf Inf Inf 1 0 2 2 1 Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf 0 Stauts = 15 3 7 1 3 6 0 0 0

예제 4.3 아래결합행렬은어느테니스경기토너먼트의결과이다. (13) 이토너먼트에얼마나많은순환적세점과얼마나많은추이적세점이있는가? >> A = [0,0,0,1,1,1,1; 1,0,1,1,0,1,0; 1,0,0,0,1,1,1; 0,0,1,0,0,1,1; 0,1,0,1,0,0,1; 0,0,0,0,1,0,0; 0,1,0,0,0,1,0]; >> score = sum(a,2)' score = 4 4 4 3 3 1 2

>> transitive = sum(score.*(score-1)/2) transitive = 25 >> n=length(a); cycle = n*(n-1)*(n-2)/6 - transitive cycle = 10 예제 4.4 예제 4.3 경기토너먼트의결과에서승수 (power) 값을구하시오. >> A = [0,0,0,1,1,1,1; 1,0,1,1,0,1,0; 1,0,0,0,1,1,1; 0,0,1,0,0,1,1; 0,1,0,1,0,0,1; 0,0,0,0,1,0,0; 0,1,0,0,0,1,0]; >> score = sum(a,2)'; >> power = score + sum(a^2,2)' power = 13 16 14 10 12 4 7

i f i f

예제 5.2 (a) A 1, A 2, A 3, A 4 각각은모두와통신한다 ( 단, 자기자신과는제외하고 ) (b) A 5 는단지 A 1 과만통신한다, (c)a 6 은 A 2, A 4, A 5 와통신한다. 위와같은성질들을가진 6 명의개인들의집합 {A 1, A 2, A 3, A 4, A 5, A 6 } 이있다고가정하자. 모든가능한군집 (cliques) 을찾아라. (( 답 )) 군집의정의로부터, 부분집합안의모든개인들의쌍사이에서양방향통신이존재하는가장큰가능한부분집합 ( 적어도 3 명이상인 ) 을찾아야만한다. 단지 2 개의군집 {A 1, A 2, A 3, A 4 } 과 {A 2, A 4, A 6 } 만이있음을알수있다. 단지 2 명뿐이기때문에부분집합 {A 1, A 5 } 는군집이아니다. 또한, 부분집합 {A 1, A 2, A 3 } 도군집이아닌데, 최대가아니기때문이다.

예제 5.4 통신네트워크에관한행렬 A가 라고가정하자. 어떤사람들이군집에속해있는가? >> A = [0 1 0 1; 1 0 0 0; 0 1 0 1; 1 0 1 0]; >> B = A.*A' B = 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0 >> B3 = B^3

B3 = 0 2 0 3 2 0 1 0 0 1 0 2 3 0 2 0

예제 5.6 행렬 A가 인통신네트워크안에서모든군집을찾아라. >> A = [0 1 1 0 1; 1 0 1 1 1; 1 1 0 1 1; 0 1 1 0 1; 1 0 1 1 0]; >> B = A.*A'; B3 = B^3, B3d = diag(b3)' B3 = 4 8 8 4 8 8 4 8 8 4 8 8 8 8 8 4 8 8 4 8 8 4 8 8 4 B3d = 4 4 8 4 4

예제 6.5 [ 그림 10-16] 에서보여지는각각의그래프에대해, ( 만약존재한다면 ) Euler 경로를찾아라. ( 만약존재한다면 ) Hamilton 경로를찾아라. [ 그림 10-16 Euler 경로와 Hamilton 경로찾기 ] (( 답 )) G 에대해점 2 와 9 는차수 3 을가진다. 모든다른점들은짝수 (2 또는 4) 차수이다. 정리 6.2 에의해, G 는닫힌 Euler 경로를갖지않지만, 정리 6.3 에의해 G 는 2 나 9 로시작해서 9 나 2 로끝나는열린 (open) Euler 경로를가진다. 그래프 H 는차수 5 인네개의점을가진다. 때문에 H 는열리거나닫힌어떤 Euler path 도갖지않는다. G 와 G 에대한 Hamilton 경로를실험에의해찾을수있다. Euler 와 Hamilton 경로는 [ 그림 10-17] 에서보여진다. G 는또한 Hamilton 서킷임을알수있다. 그러나 H 는 Hamilton 서킷이아니다.

[ 그림 10-17 Euler 경로와 Hamilton 경로 ]