루프 (그래프 이론)

그래프 이론에서 루프(loop)는 하나의 정점에서 시작하여 그 자신, 즉 동일한 정점으로 끝나는 간선을 가리킨다. 이는 두 개의 서로 다른 정점을 연결하는 일반적인 간선과 구분되는 개념이다. 수학적으로 정점 *v*에 대한 루프는 순서쌍 *(v, v)* 또는 집합 *{v, v}*로 표기된다.

루프는 방향 그래프와 무방향 그래프 모두에서 정의될 수 있다. 유향 그래프에서의 루프는 명시적인 방향을 가지며, 정점에서 나와서 다시 그 정점으로 들어오는 형태를 이룬다. 반면 무향 그래프에서의 루프는 방향성이 없으며, 정점을 자기 자신과 연결하는 하나의 고리로 표현된다. 이러한 루프의 존재 여부는 그래프의 종류를 정의하는 중요한 기준 중 하나가 된다. 예를 들어, 단순 그래프는 루프와 다중 간선을 모두 허용하지 않는 반면, 다중 그래프나 유사 그래프는 루프를 포함할 수 있다.

그래프 이론에서 루프는 하나의 정점에서 시작하여 같은 정점으로 끝나는 간선이다. 이러한 루프는 다시 단순 루프와 다중 루프로 구분된다. 단순 루프는 하나의 정점에 단 하나의 루프만 존재하는 경우를 말한다. 반면, 다중 루프는 하나의 정점에 두 개 이상의 루프가 연결된 경우를 의미하며, 이는 다중 그래프에서만 허용되는 개념이다.

무방향 그래프에서 루프는 일반적으로 정점 v에 대해 집합 {v, v}로 표기한다. 이는 순서쌍 (v, v)로 표기하는 유향 그래프의 루프와 구분된다. 루프의 존재 여부는 그래프의 종류를 정의하는 중요한 기준이 된다. 예를 들어, 단순 그래프는 루프와 다중 간선을 모두 허용하지 않는다.

루프는 해당 정점의 차수 계산에 특별한 영향을 미친다. 무방향 그래프에서 하나의 루프는 시작점이자 끝점인 정점의 차수에 2를 기여한다. 이는 루프가 해당 정점에 두 번 연결된 것으로 간주하기 때문이다. 이러한 성질은 인접 행렬을 통한 그래프 표현에서도 확인할 수 있으며, 알고리즘 설계 시 고려해야 할 요소가 된다.

그래프 이론에서 정점의 차수는 그 정점에 연결된 간선의 수를 의미한다. 일반적인 간선은 양쪽 끝점의 차수에 각각 1씩 기여하지만, 루프는 특별한 방식으로 차수에 영향을 미친다.

무방향 그래프에서 하나의 루프는 해당 정점의 차수에 2를 기여한다. 이는 루프가 하나의 정점을 두 번 연결하는 것으로 간주되기 때문이다. 예를 들어, 정점 v에 하나의 루프가 있고 다른 간선이 없다면, 정점 v의 차수는 2가 된다. 이 규칙은 그래프의 총 차수 합이 간선 수의 두 배가 된다는 핸드셰이킹 보조정리가 성립하도록 하기 위한 것이다.

유향 그래프에서는 상황이 다르다. 유향 그래프에서 차수는 진입차수와 진출차수로 나뉜다. 하나의 방향 루프는 해당 정점의 진입차수와 진출차수에 각각 1씩 기여한다. 따라서 정점 v에 하나의 방향 루프만 존재한다면, v의 진입차수와 진출차수는 모두 1이 된다.

루프가 차수에 미치는 이러한 영향은 다양한 그래프 알고리즘과 정리에서 중요한 요소로 작용한다. 예를 들어, 오일러 경로나 해밀턴 경로를 판별할 때, 또는 정점의 차수를 기반으로 하는 그래프 불변량을 계산할 때 루프의 처리를 명확히 고려해야 한다.

그래프 이론에서 인접 행렬은 그래프의 구조를 행렬 형태로 표현하는 방법이다. 루프가 있는 그래프의 인접 행렬 표현은 루프가 없는 경우와 차이가 있다.

무방향 그래프에서, 정점 v에 연결된 하나의 루프는 해당 정점의 차수에 2를 기여한다. 이는 인접 행렬에서도 반영되어, 대각선 상의 원소 a_{vv} (정점 v에 해당하는 행과 열이 교차하는 위치)의 값이 1이 아닌 2로 표기된다. 즉, 루프는 정점이 자기 자신과 두 번 연결된 것으로 간주하여 행렬에 기록된다. 반면, 유향 그래프에서의 루프는 일반적으로 대각선 원소를 1로 표시하여, 정점에서 나가서 다시 들어오는 하나의 방향 간선임을 나타낸다.

인접 행렬은 그래프의 연결 관계를 명확하게 보여주지만, 루프와 다중 간선을 모두 표현할 수 있는 다중 그래프의 경우, 행렬의 각 원소가 간선의 개수(중복도)를 나타내도록 확장하여 사용하기도 한다. 이러한 표현은 컴퓨터 알고리즘, 특히 그래프 알고리즘을 구현할 때 그래프의 구조를 효율적으로 저장하고 처리하는 데 활용된다.

다중 그래프는 그래프 이론에서 두 정점 사이에 여러 개의 간선이 존재할 수 있으며, 루프 또한 허용되는 그래프의 한 종류이다. 이는 가장 일반적인 그래프 모델 중 하나로, 복잡한 관계나 다중 연결을 표현하는 데 적합하다. 다중 그래프는 단순 그래프와 구분되는 개념으로, 단순 그래프는 두 정점 사이에 최대 하나의 간선만을 허용하고 루프를 금지한다.

다중 그래프에서 루프는 하나의 정점에서 시작하여 같은 정점으로 돌아오는 간선을 의미한다. 이러한 루프는 무방향 그래프에서는 집합 {v, v}로, 유향 그래프에서는 순서쌍 (v, v)로 표기된다. 루프의 존재는 그래프의 인접 행렬 표현에도 영향을 미치며, 특히 무방향 그래프에서 루프는 해당 정점의 차수를 2만큼 증가시킨다.

다중 그래프와 루프는 네트워크 이론, 화학 그래프, 전기 회로 분석 등 다양한 분야에서 응용된다. 예를 들어, 분자 구조를 나타내는 화학 그래프에서 루프는 원자 내의 특수한 결합을 나타낼 수 있으며, 통신 네트워크 모델에서는 하나의 노드가 자기 자신과의 통신 채널을 가짐을 표현할 수 있다.

유향 그래프에서의 루프는 방향을 가진 간선이 하나의 정점에서 시작하여 그 정점 자체로 다시 돌아오는 것을 의미한다. 이러한 간선은 (v, v)와 같은 순서쌍으로 표기된다. 유향 그래프에서 루프는 해당 정점에 대한 '자기 참조'나 '자기 순환' 관계를 모델링하는 데 사용된다. 예를 들어, 어떤 작업이 자기 자신을 필요로 하거나, 어떤 상태가 자기 자신으로의 전이를 허용하는 경우를 표현할 수 있다.

유향 루프는 정점의 차수에 영향을 미친다. 유향 그래프에서 정점의 차수는 진입차수와 진출차수로 나뉜다. 하나의 유향 루프는 시작점과 끝점이 동일한 정점이므로, 해당 정점의 진입차수와 진출차수에 각각 1씩을 기여한다. 따라서 하나의 루프는 해당 정점의 총 차수(진입차수와 진출차수의 합)에 2를 더하게 된다.

인접 행렬로 유향 그래프를 표현할 때, 루프는 주대각선 상의 원소로 나타난다. 정점 v_i에 대한 루프가 존재한다면, 인접 행렬의 (i, i) 위치의 값은 일반적으로 1(또는 간선의 가중치)이 된다. 이는 무방향 그래프의 인접 행렬에서 루프가 주대각선에 2의 값을 갖는 것과 구별되는 특징이다[2].

유향 루프를 포함하는 그래프는 다중 그래프의 한 유형으로 분류될 수 있으며, 오토마타 이론, 상태 머신, 순환 의존성을 분석하는 소프트웨어 공학 등 다양한 분야에서 응용된다. 반면, 단순 그래프의 정의에는 일반적으로 루프와 다중 간선이 허용되지 않는다.

단순 그래프는 그래프 이론에서 가장 기본적이고 제약이 많은 그래프 모델 중 하나이다. 이 모델은 두 정점 사이에 최대 하나의 간선만 존재할 수 있으며, 루프가 전혀 허용되지 않는다는 특징을 가진다. 즉, 어떤 정점도 자기 자신과 직접 연결되는 간선을 가질 수 없다. 이러한 엄격한 정의는 복잡한 연결 관계를 단순화하여 분석하기 쉽게 만들며, 많은 고전적인 그래프 문제와 알고리즘의 기초가 된다.

단순 그래프의 이러한 제약은 수학적 모델링의 명확성을 높인다. 예를 들어, 친구 관계를 나타내는 소셜 네트워크 그래프에서 한 사람이 자기 자신과 친구일 수는 없으므로, 이는 단순 그래프로 자연스럽게 표현된다. 또한 화학에서 분자 구조를 나타내는 그래프에서 원자는 동일한 원자와 화학 결합을 형성하지 않으므로, 단순 그래프가 적합한 표현 도구가 된다.

루프를 배제함으로써 그래프의 차수 계산이 단순해진다. 무방향 단순 그래프에서 어떤 정점의 차수는 단순히 그 정점에 인접한 다른 정점들의 개수와 일치한다. 이는 루프가 존재할 경우 해당 정점의 차수에 2를 기여하여 계산을 복잡하게 만드는 것과 대비된다. 많은 그래프 정리와 공식, 예를 들어 악수 정리는 단순 그래프를 전제로 증명된다.

단순 그래프는 완전 그래프, 경로 그래프, 사이클 그래프와 같은 많은 중요한 그래프 족의 기초가 된다. 또한 그래프 동형, 그래프 색칠 문제와 같은 핵심 연구 분야에서 표준적인 연구 대상이다. 루프와 다중 간선이 허용되는 다중 그래프나 유사 그래프와는 구분되는, 그래프 이론의 핵심적인 기본 구조를 제공한다.

그래프 순회 알고리즘을 설계하거나 구현할 때, 루프의 존재는 특별한 고려가 필요하다. 깊이 우선 탐색이나 너비 우선 탐색과 같은 기본적인 순회 알고리즘은 일반적으로 각 정점을 한 번만 방문하도록 설계되어 있다. 루프는 시작 정점과 도착 정점이 동일하기 때문에, 순회 과정에서 현재 정점에서 자기 자신으로 가는 간선을 탐색하게 되면, 이는 새로운 미방문 정점으로의 이동으로 간주되지 않는다. 따라서 대부분의 구현에서는 루프를 무시하거나, 특별한 처리를 하지 않고 그냥 지나치게 된다. 이는 알고리즘이 무한 루프에 빠지는 것을 방지하기 위함이다.

그러나 인접 행렬을 사용한 그래프 표현에서는 루프가 명시적으로 드러난다. 대각선 상의 값, 즉 A[i][i]가 1(또는 가중치)인 경우, 이는 정점 i에 루프가 존재함을 의미한다. 순회 알고리즘이 인접 행렬을 사용한다면, 이 대각선 원소를 확인할 때 특별한 로직을 추가하여 처리해야 할 수 있다. 예를 들어, 해당 정점의 차수를 계산하거나 그래프의 특정 성질을 분석할 때는 루프를 고려해야 하지만, 단순히 모든 정점을 방문하는 순회 목적에서는 이를 스킵하는 것이 일반적이다.

일부 알고리즘 문제나 응용 분야에서는 루프가 중요한 의미를 가질 수 있다. 예를 들어, 상태 머신 모델링이나 특정 정점에서의 자기 반복을 나타내는 경우, 알고리즘이 루프를 인식하고 이에 따른 추가 동작(예: 카운트 증가, 상태 변경)을 수행하도록 요구할 수 있다. 따라서 그래프 순회 알고리즘을 작성할 때는 입력 그래프에 루프가 포함될 수 있는지 여부를 사전에 확인하고, 이에 맞는 적절한 처리 방식을 결정하는 것이 중요하다.

인접 리스트는 그래프 (자료 구조)를 표현하는 일반적인 방법 중 하나이다. 이 표현 방식에서 각 정점은 자신과 인접한 다른 정점들의 목록을 가진다. 루프가 존재하는 경우, 이는 하나의 정점이 자기 자신과 인접함을 의미하므로, 인접 리스트에서 특별한 처리가 필요하다.

일반적으로 정점 v에 대한 루프는 해당 정점의 인접 리스트에 v 자신을 한 번 추가하여 표현한다. 예를 들어, 정점 A에 루프가 있다면, A의 인접 리스트는 [A, ...]와 같은 형태가 된다. 이는 인접 행렬에서 루프가 대각선 원소에 1(또는 가중치)로 표시되는 것과 대조적이다. 일부 구현에서는 루프를 명시적으로 구분하기 위해 특별한 마커나 플래그를 사용하기도 한다.

그래프 순회나 알고리즘을 구현할 때, 인접 리스트의 루프 처리는 주의가 필요하다. 예를 들어, 깊이 우선 탐색을 수행할 때 정점을 자신의 인접 리스트에서 다시 발견하면, 이를 이미 방문한 다른 정점으로 간주하여 무한 루프에 빠지지 않도록 적절히 처리해야 한다. 마찬가지로 너비 우선 탐색에서도 큐에 동일한 정점이 중복 삽입되는 것을 방지하는 로직이 필요하다.

인접 리스트는 희소 그래프를 표현하는 데 공간 효율적이지만, 루프의 존재는 알고리즘의 논리적 복잡성을 약간 증가시킨다. 따라서 그래프를 처리하는 라이브러리나 프레임워크는 내부적으로 루프를 포함한 다양한 그래프 구조를 안정적으로 지원하기 위한 방안을 마련하고 있다.

그래프 이론에서 사이클은 하나의 정점에서 시작하여 동일한 정점으로 돌아오는, 서로 다른 정점과 간선을 순차적으로 지나는 폐쇄된 경로를 의미한다. 이는 루프와 구별되는 중요한 개념으로, 루프가 단일 정점과 단일 간선으로 구성된 반면, 사이클은 최소 3개 이상의 서로 다른 정점과 간선을 포함해야 한다는 점이 다르다. 사이클은 그래프의 순환 구조를 파악하는 데 핵심적이며, 트리와 같은 비순환 그래프를 정의하는 기준이 된다.

사이클은 길이에 따라 분류될 수 있다. 예를 들어, 3개의 정점으로 이루어진 사이클을 삼각형이라고 부르며, 그래프 내의 군집 구조를 분석할 때 중요한 지표로 활용된다. 한편, 해밀턴 경로 문제나 외판원 문제와 같은 유명한 조합 최적화 문제들은 본질적으로 그래프에서 특정 조건을 만족하는 사이클을 찾는 문제와 깊은 연관이 있다.

루프와 사이클은 모두 폐쇄된 구조를 가지지만, 그 구성과 의미에서 명확한 차이가 있다. 루프는 정점 자체에 대한 자기 연결을 나타내는 반면, 사이클은 여러 정점을 순환하는 더 큰 구조를 설명한다. 따라서 많은 알고리즘과 이론에서는 루프를 허용하더라도 사이클의 존재 여부를 별도로 판단하며, 이는 그래프의 위상적 성질을 이해하는 데 필수적이다.

자기 동형사상은 그래프 이론에서 그래프의 구조를 보존하는 전단사 함수이다. 구체적으로, 그래프 G에서 그래프 G 자신으로 가는 동형사상을 의미한다. 이는 그래프의 정점들을 재배열하되, 정점들 사이의 인접 관계를 그대로 유지하는 순열에 해당한다. 모든 그래프는 항상 항등 함수라는 자기 동형사상을 가지며, 이는 가장 단순한 예이다.

자기 동형사상의 집합은 함수의 합성 연산 아래에서 군을 이루며, 이를 그래프의 자기 동형사상군이라고 부른다. 이 군의 구조를 분석하는 것은 그래프의 대칭성을 이해하는 핵심 도구가 된다. 예를 들어, 완전 그래프나 정다각형의 그래프는 매우 높은 수준의 대칭성을 가지며, 이는 큰 자기 동형사상군으로 나타난다.

루프를 가진 그래프에서 자기 동형사상은 루프의 존재에 의해 제약을 받는다. 자기 동형사상은 정점의 인접 관계를 보존해야 하므로, 루프를 가진 정점은 반드시 다른 루프를 가진 정점으로만 매핑될 수 있다. 따라서 그래프에 루프가 있는 정점과 없는 정점이 섞여 있다면, 이 두 종류의 정점 집합 사이에는 매핑이 발생할 수 없어 그래프의 대칭성이 제한된다.

자기 동형사상의 개념은 화학에서 분자의 대칭성을 연구하거나, 네트워크 과학에서 복잡계의 구조적 패턴을 분석하는 등 다양한 분야에 응용된다. 또한 그래프 동형 문제와 깊은 연관이 있으며, 코딩 이론이나 조합론에서도 중요한 역할을 한다.