일반적으로, 다양한 기본적 타입의 그래프가 존재한다.
이 섹션에서는 몇개의 기본적 타입의 그래프를 살펴보게 된다.
Null 그래프.
null 그래프는 노드의 set이 0으로 되어 있는 그래프이다(노드가 없는 상황을 의미한다).
당연하겟지만 노드가 없으니 엣지도 없다.
수식으로 표현하면 다음처럼 표현이 가능하다.
비어있거나 엣지가 없는 그래프를 비어있는 그래프라 한다.
노드의 SET은 비어있을수 있다.
NULL 그래프는 비어있을수 있지만 반대는 성립하지 않는다.
Directed/Undirected/Mixed Graphs. 지정된/비지정된/혼합된 그래프.
지금까지 우리가 살펴본 그래프중 Directed 그래프는 거의 없었다.
언급했듯이,그래프중 directed 엣지만 있는 상황을 directed 그래프라고 하며 undirected 엣지만 있다면 undirected 그래프라고 한다.
Mixed그래프는 directed undirected 의 성격을 모두 가지고 있다.
directed 그래프에서, i와 j 두개의 엣지가 있다(i에서 j방향으로 가는 방향),undirected 그래프는 한개의 엣지만 존재한다.
결과적으로, directed 그래프의 인접 행렬는 일반적인 대칭이 아니다 (i 에서 j로 가는 연결성은 j에서 i 방향으로 가는 것과는 다름), undirected 그래프에서 인접 행렬 대칭성을 가진다.
소셜 미디어에서는, 다양한 directed 와 undirected 네트워크가 존재한다.
예를들면, 페이스북은 undirected 네트워크인데 만약 jon과 mary가 친구라고 했을때, mary는 동시에 jon과 친구이다.
트위터는 directed 네트워크라고 생각할수 있다,팔로워와 팔로잉 하는 사람은 양방향성을 가지지 않기 때문이다.
한 방향은 팔로워, 다른 방향은 팔로잉이라고 할수있다.
simple 그래프와 multi 그래프.
지금까지 제공된 예시 그래프는, 두개의 노드의 쌍 사이에 하나의 엣지만 존재했다.
이 그래프는 간단한 상태를 나타내고 있다.
Multi그래프의 정의는 두개의 노드상에 다수의 엣지가 있는 상태를 의미한다.
multi 그래프에 대한 근접행렬은 일반적 상황의 근접 행렬보다 크며, 두개의 노드사이에 다수의 엣지가 존재함을 표시한다.
multi 그래프는 소셜 미디어에서 자주 관찰되는데 두개의 노드가 있다면 서로 다른 상호작용을 낼때 확인이 가능하다.
해당 노드들은 친구일수도, 동시에 동료이며, 그룹맴버이거나, 다른 관계를 이룰수 있기 때문이다.
이런 관계들 사이에서, 새로운 엣지가 두개의 개개인 사이에 추가 될수 있는데, 이때 multi그래프가 생성된다.
가중치 그래프.
가중치 그래프란 엣지들중 하나가 가중치를 가질때 사용된다.
예를들면, 지도를 의미하는 그래프가 있다고 하자, 각 노드는 도시를, 엣지는 도시를 연결하는 루트(길)가 된다.
이때 가중치란 각 도시 사이의 거리라 할 수 있다.
일반적으로, 가중치 그래프는 그래프G(V,E,W) 로 표시하는데 W는 각 엣지에 대한 가중치 수치를 표현한다 |W|=|E|의 상황이다.
근접 행렬로 표현하면, 1/0으로 표현하는것 대신에, 각 엣지에 해당하는 가중치를 사용할수 있다.
이런 표현 방식을 사용하면 근접 행렬A에서 E,W의 혼합 경로에서의 용량을 줄일수 있다, i에서 j로 가는 엣지가 있으며 가중치가 0이 아니라고 가정해보면.
내용에 따라 다르겟지만, 이 가중치는 Wij 나 w(i,j)만 사용해서 나타낼수 있다.
가중치 그래프의 예로 웹 그래프를 들수 있다.
웹 그래프는 어떻게 인터넷 사이트들이 웹에 연결되어 있는지 보여주는 한가지 방식이다.
일반적으로, 웹그래프는 방향성을 가지는 그래프이다.
각 노드는 사이트를 의미하고 엣지의 가중치는 사이트간의 링크를 의미한다.
구개의 사이트는 다수의 링크를 가지고 서로를 가리킬수 있으며 각 사이트는 루프링크(링크를 누르면 다시 현재 사이트에 접속하는것, 접속 사이트 이미지를 누르면 자신에게 돌아오는것과 같은 원리).
특별한 가중치 그래프가 있는데 양자 택일(binary) 가중치를 가지는 그래프로서 엣지에 (0/1 이나 +/-)을 가지는 그래프이다.
이런 엣지들은 일반적으로 signed엣지라고 부르며, 이런 가중치 그래프를 signed 그래프라 한다.
signed 엣지는 모순된 상황에서 사용될수 있다.
예를들면, 관계를 나타내는 엣지에서 친구이자 적의 상황에서 사용할수 있다.
두개의 노드 사이에 긍정적(+) 엣지가 있다면 친구 관계를, 부정적인(-) 엣지가 있다면 적대 관계를 가진다고 볼수 있다.
엣지가 방향성을 가진다면, 하나의 종착지점 노드는 상대의 친구이거나 적이 될수있다, 하지만 그 역은 성립하지 않는다.
엣지가 방향성을 가지지 않는다면, 종착지점 노드는 서로 친구 사이거나 적일수 있다.
다른 설정상에선, + 엣지는 높은 사회적 위치를 의미할수 있고, 반대로 - 엣지는 낮은 사회적 위치를 의미한다.
사회적 지위의 정의를 사회에서 자신의 지위에 배정된 계급으로 볼수 있다.
예를들면, 학교라는 사회에서 교장선생님의 위치는 학생에서 출발하는 엣지에서는 +를 가진다,학교내에서는 교장선생님이 학생들보다는 높은 지위를 가지기 때문이다.
그림 2.5의 그래프를 보면 signed 그래프 상에서의 상호 관계를 의미한다.
그림 2.5 signed 그래프의 예시.
댓글 없음:
댓글 쓰기