아무 말

보호되어 있는 글입니다.

인접 행렬 인접 행렬(Adjacency matrix) 그래프를 나타내기 위한 방법 중 하나로, 다른 방법으로는 인접 리스트(Adjacency list)가 있습니다. 인접 행렬의 \((i,j)\) 항은 정점 \(i\)로 부터 \(j\)로 뻗어 나가는 간선의 개수입니다. 왼쪽의 그래프와 인접 행렬을 보면 알 수 있듯이, 무향 그래프에서의 인접 행렬은 대칭 행렬입니다. 이에 반해서, 유향 그래프의 인접 행렬은 대칭 행렬이 아닐 수 있습니다. (모든 간선에 대해 그 간선의 역방향 간선이 존재한다면, 인접 행렬이 대칭 행렬이 된다.) 인접 행렬의 유명한 성질 중 하나는 행렬의 n승의 항이 정점 i에서 j로의 n개의 간선을 이용하는 보행의 수입니다. 이는 무향 그래프이든 유향 그래프이든 관계없이 성립하게 됩니다. ..

그래프는 정점(Vertex)의 집합과 간선(Edge)의 집합으로 이루어져 있습니다. 조금 더 직관적으로는 점과 그 점 사이를 잇는 선분으로 이루어진 그림이라고 할 수 있겠습니다. 참고로, 정점은 꼭짓점이나, 노드(Node)라고 부르기도 합니다. 간단하게 용어를 정리하자면 정점(Vertex) 그래프의 정점 간선(Edge) 그래프의 두 정점을 잇는 간선 루프(Loop) 하나의 정점만을 연결하는 간선 보행(Walk) 정점과 간선을 이용하여 나타낸 열. 이때, 정점과 정점 사이에 나오는 간선은 두 정점을 연결한다. 보행에서 시작하는 정점과 끝나는 정점이 같을 경우, 이 보행은 닫혀있으며, "닫힌 보행(Closed Walk)"이라고 한다. 트레일(Trail) 간선이 중복되지 않는 보행 경로(Path) 정점이 중복..