| 1 |
1
노드와 에지로 구성된 2차원 그래프를 전기 회로적으로 해석하여 노드의 각 레벨을 나타내는 원형궤도 상에 각 노드의 전위를 노드 열(column)로 나타내는 3차원 전위 그래프로 생성하는 단계;상기 3차원 전위 그래프에서 원점(O), 시작 노드(S) 및 터미널 노드(T)를 연결하여 직각 삼각형을 구성하는 단계;상기 직각 삼각형의 빗변(ST)의 길이보다 작은 양의 실수 중에서 선택된 최대전압(Vmax)을 상기 2차원 그래프의 전체 전압으로 추정하는 단계;상기 2차원 그래프의 각 에지 비용을 대응하는 저항으로, 상기 최대전압(Vmax)을 상기 2차원 그래프의 전체 전압으로 설정하여, 상기 2차원 그래프의 각 에지에 흐르는 부 전류를 설정하는 단계; 및각 에지의 부 전류를 추정하는 상기 KCL 및 KVL의 선형 연립 방정식을 이용하여 일부 에지를 제거하는 단계;를 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 2 |
2
제1항에 있어서, 상기 3차원 전위 그래프로 생성하는 단계는,상기 2차원 그래프에 가상의 전위를 적용하고 시작 노드(S) 및 터미널 노드(T) 사이의 에지를 전기 회로의 저항으로 가정하여, 상기 2차원 그래프를 전기 회로적으로 해석하는 단계;상기 2차원 그래프에서 시작 노드(S)와의 사이의 최소 에지의 수를 나타내는 레벨이 동일한 노드끼리 그룹화하여 레벨 단위 변환 그래프를 생성하는 단계; 및각 노드의 전위 값을 노드 열(column)의 높이 값으로 매핑하여 해당하는 레벨을 나타내는 원형 궤도 상에 배치하여 3차원 전위 그래프를 생성하는 단계;를 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 3 |
3
제2항에 있어서, 상기 3차원 전위 그래프로 생성하는 단계는,상기 3차원 전위 그래프의 각 레벨의 원형 궤도에서 각 노드 열의 위치를 이동하여 하나의 평면 상에 직선으로 정렬하는 단계;를 더 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 4 |
4
제1항에 있어서, 상기 직각 삼각형을 구성하는 단계는,상기 3차원 전위 그래프에서 시작 노드 열의 가장 높은 지점을 시작 노드(S)로, 터미널 노드 열의 가장 낮은 지점을 터미널 노드(T)로, 시작 노드 열의 바닥 지점을 원점(O)으로 설정하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 5 |
5
제1항에 있어서, 상기 2차원 그래프의 전체 전압으로 추정하는 단계는,상기 직각 삼각형의 빗변(ST)의 길이를 추정하는 단계;를 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 6 |
6
제5항에 있어서, 상기 2차원 그래프의 전체 전압으로 추정하는 단계는,상기 2차원 그래프의 전체 전압은 변(SO)의 길이와 같은 레벨 0인 노드의 전위와 같고, 상기 빗변(ST)은 이상적인 노드를 통과하는 최단 직선 거리로 정의하는 단계;를 더 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 7 |
7
제6항에 있어서, 상기 2차원 그래프의 전체 전압으로 추정하는 단계는,N 레벨 그래프의 빗변(ST)을 인접한 레벨 사이의 최소 비용의 합이라고 가정하여 레벨 k-1과 레벨 k 사이의 에지 비용을 정의하는 단계(여기서 N과 k는 양의 정수, 1 ≤ k ≤ N);를 더 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 8 |
8
제7항에 있어서, 상기 2차원 그래프의 전체 전압으로 추정하는 단계는,N 레벨 그래프의 전체 전압을 레벨 k-1과 레벨 k 사이의 최소 비용의 합보다 작은 양의 값으로 추정하는 단계;를 더 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 9 |
9
제1항에 있어서, 상기 2차원 그래프의 각 에지에 흐르는 부 전류를 설정하는 단계는,전위가 최대전압(Vmax)인 시작 노드(S)에서 전위가 0인 터미널 노드(T)로 흐르는 전류를 이용하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 10 |
10
제1항에 있어서, 상기 일부 에지를 제거하는 단계는,부 전류가 0인 에지를 제거하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 11 |
11
제1항에 있어서,에지가 제거된 상기 2차원 그래프에서 최단 경로 또는 최소 비용 경로를 선택하는 단계;를 더 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법
|
| 12 |
12
제1항 내지 제11항 중 어느 하나의 항에 따른 상기 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법을 수행하기 위한 컴퓨터 프로그램이 기록된 컴퓨터로 판독 가능한 저장 매체
|
| 13 |
13
노드와 에지로 구성된 2차원 그래프를 전기 회로적으로 해석하여 노드의 각 레벨을 나타내는 원형궤도 상에 각 노드의 전위를 노드 열(column)로 나타내는 3차원 전위 그래프로 생성하는 그래프 변환부;상기 3차원 전위 그래프에서 원점(O), 시작 노드(S) 및 터미널 노드(T)를 연결하여 직각 삼각형을 구성하는 그래프 분석부;상기 직각 삼각형의 빗변(ST)의 길이보다 작은 양의 실수 중에서 선택된 최대전압(Vmax)을 상기 2차원 그래프의 전체 전압으로 추정하는 전압 추정부;상기 2차원 그래프의 각 에지 비용을 대응하는 저항으로, 상기 최대전압(Vmax)을 상기 2차원 그래프의 전체 전압으로 설정하여, 상기 2차원 그래프의 각 에지에 흐르는 부 전류를 설정하는 전류 추정부; 및각 에지의 부 전류를 추정하는 상기 KCL 및 KVL의 선형 연립 방정식을 이용하여 일부 에지를 제거하는 에지 제거부;를 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 장치
|
