대학보유기술

중앙대학교에서 보유하고 있는 기술 입니다.
클릭 시 상세 정보 확인 및 상담신청이 가능합니다.

상담신청

보유기술정보
출원번호 / 일자	1020200133692 (2020-10-15)
등록번호 / 일자	1024338970000 (2022-08-12)
발명자	고려대학교 산학협력단,중앙대학교 산학협력단
기술명	키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법, 이를 수행하기 위한 기록 매체 및 장치

요약

키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법은, 노드와 에지로 구성된 2차원 그래프를 전기 회로적으로 해석하여 노드의 각 레벨을 나타내는 원형궤도 상에 각 노드의 전위를 노드 열(column)로 나타내는 3차원 전위 그래프로 생성하는 단계; 상기 3차원 전위 그래프에서 원점(O), 시작 노드(S) 및 터미널 노드(T)를 연결하여 직각 삼각형을 구성하는 단계; 상기 직각 삼각형의 빗변(ST)의 길이보다 작은 양의 실수 중에서 선택된 최대전압(V max )을 상기 2차원 그래프의 전체 전압으로 추정하는 단계; 상기 2차원 그래프의 각 에지 비용을 대응하는 저항으로, 상기 최대전압(V max )을 상기 2차원 그래프의 전체 전압으로 설정하여, 상기 2차원 그래프의 각 에지에 흐르는 부 전류를 설정하는 단계; 및 각 에지의 부 전류를 추정하는 상기 KCL 및 KVL의 선형 연립 방정식을 이용하여 일부 에지를 제거하는 단계;를 포함한다. 이에 따라, 네트워크 분야의 검색 문제 혹은 경로 탐색 문제에서 그래프를 최적화할 수 있다.

목록 상담신청