초록 ▼

앞서 노유미 교수님은 Ilić, Klavžar와 함께 피보나치류의 일반화로서, 주어진 수열을 부분수열로 포함하지 않는 차원 이진수열에 유도된 부분그래프를 ‘일반화된 피보나치 큐브(Generalized Fibonacci cubes)’라 명명하고 이 때 주어진 수열을 ‘금지된 수열(forbidden string)’이라 명명했다.

일반화된 피보나치 큐브가 하이퍼 큐브로 등거리 매장이 가능한지에 대한 질문은 금지된 수열에 크게 의존한다. 따라서 일반화된 피보나치 큐브 Q_d(f)가 항상 Q_d

앞서 노유미 교수님은 Ilić, Klavžar와 함께 피보나치류의 일반화로서, 주어진 수열을 부분수열로 포함하지 않는 차원 이진수열에 유도된 부분그래프를 ‘일반화된 피보나치 큐브(Generalized Fibonacci cubes)’라 명명하고 이 때 주어진 수열을 ‘금지된 수열(forbidden string)’이라 명명했다.

일반화된 피보나치 큐브가 하이퍼 큐브로 등거리 매장이 가능한지에 대한 질문은 금지된 수열에 크게 의존한다. 따라서 일반화된 피보나치 큐브 Q_d(f)가 항상 Q_d로 등거리 매장 될 경우f를 좋은수열이라고 부른다. 이 경우 좋은 수열의 비율이 약 8%정도라는 것이 알려져 있다. 노유미 교수 님은 [1]의 논문에서 Ilić, Klavžar와 함께 주어진 수열 f가 좋은 수열인지를 판별하는 지수(index)를 제시하였고, 대부분의 좋지 않은 수열 f에 대하여 β(f)<2lfl라는 것을 알아내었다. 이는 어떤 수열이 좋은 수열인지를 확인하기 위해서는 1≤ d≤2lfl에 대해 Q_d(f)가 Q_d로 등거리 매장된다는 것만 확인하면 된다는 의미이다. 또한 이를 증명하는 과정에서 자연스럽게 등장한 등거리 매장보다 약한 성질인 2-등거리 매장에 대하여 탐구하였다.

또한 본 연구에서는 Q_d(f)의 각 이진 수열을 단어라 명명하고, 단어는 자릿수의 합이 짝수이면 짝수 단어, 홀수이면 홀수 단어라 명명했다 [2].Q_d(f)는 짝수 단어의 집합과 홀수 단어의 집합으로 분할된다. 어떤 공간의 분할에서 각 부분의 크기가 고르다는 성질은 조합론이나 그래프 이론에서 관심있는 성질이다. 우리는 짝수 단어의 수와 홀수 단어의 수의 차가 1이하일 때, Q_d(f)가 ‘균형있다(balanced)’라고 정의했는데,Q_d(f)는 균형 있다면 해밀톤 경로를 가지는 등 좋은 성질을 가진다. 노유미 교수님은 Klavžar 교수, Ilić 교수와 함께 금지된 수열 중 어느 수열 f에 관하여 Q_d(f)가 균형 있는지 알아보는 문제를 제기하였다. 또한 모든 차원 d에 대하여,Q_d(f)가 균형 있는 f의 충분조건을 제시하였다.

일반화된 피보나치 큐브가 어떤 경우에 잘 알려진 그래프들의 카테지안 곱으로 표현될 수 있는지에 대한 연구는 [3]에 제시되었다.

일반화된 피보나치 큐브의 특별한 형태인 Q_d(1^s)의 비너 지수를 구하였고 특히 Q_d(111)의 비너 지수를 닫힌 형식으로 표현하였다. 또한 같은 방법으로 s>3에 대한 비너지수를 닫힌 형식으로 구할 수 있다. 같은 논문에서 f가 좋은 수열이 아닐 때, 즉 모든 에 대하여 자연스러운 매장 Q_d(f)↪Q_d가 등거리매장이 되지 못할 때 그래프 Q_d(f)의 반지름이 무한정 커질 수 있다는 것을 밝혀내었다. 이와 같은 주장이 일반화된 루카 큐브 (수식)에서도 성립한다.

또한 피보나치 큐브와 루카 큐브의 경우 그래프의 점 연결도와 선분 연결도가 모두 그래프의 최소 차수와 같다는 것을 증명하였고, 일반화된 피보나치 큐브의 경우 점 연결도가 2 이상이라는 것을 알아내었다.

마지막으로 일반화된 피보나치 큐브를 인지하는 문제에 있어서 주어진 그래프가 Q_d(111)과 동형임을 선형 시간 안에 인지하는 알고리즘을 찾아내었다.

(출처:연구결과 요약문 p.4)

목차 Contents

• 표지 ... 1목차 ... 3Ⅰ. 연구결과 요약문 ... 4Ⅱ. 연구내용 및 결과 ... 5 1. 연구과제의 개요 ... 5 2. 국내외 기술개발 현황 ... 5 3. 연구수행 내용 및 결과 ... 5 4. 목표 달성도 및 관련 분야에의 기여도 ... 6 5. 연구결과의 활용계획 ... 6 6. 연구과정에서 수집한 해외과학기술정보 ... 6Ⅲ. 연구성과 ... 7끝페이지 ... 7