6편의 한국어 분석 — 최신순으로 정렬했어요
가중치 에지 다중 절단(Edge Multiway Cut) 문제는 최대 차수 3의 평면 그래프에서 NP-완전임이 알려져 있습니다. 반면, 비가중치 버전은 최대 차수 11의 평면 그래프에서만 NP-완전성이 증명되었으며, 최대 차수 3 그래프에서의 복잡성은 20년 이상 미해결 과제로 남아 있었습니다. 본 연구는 비가중치 에지 다중 절단 문제가 최대 차수 3의 평면 그래프에서도 NP-완전임을 증명하여, 기존의 복잡성 간극을 해소했습니다. 가중치 에지 다중 절단이 최대 차수 2 이하 그래프에서 다항 시간 내에 해결 가능함을 고려할 때, 이…
그래프 버닝은 소셜 영향력 확산 모델에서 파생된 개념으로, 버닝 넘버는 확산 속도를 측정합니다. 본 연구는 주어진 버닝 넘버에 대해 차수(order) 측면에서 극단적인 그래프의 특성을 규명하는 자연스러운 문제에 주목합니다. 연결 그래프의 버닝 넘버는 해당 그래프의 신장 트리 중 하나에 의해 결정되므로, 극단 트리에 대한 연구는 이 문제 해결에 중요한 통찰을 제공합니다. 이에 따라 본 연구는 주어진 버닝 넘버를 갖는 극단 트리를 그래프 동형(homeomorphism)까지 식별하는 데 중점을 둡니다. 이를 위해 동형적으로 기약 불가능…
본 연구는 밀집 그래프 계열의 계수 시퀀스를 체계적으로 계산하기 위한 새로운 점근 확장 방법론을 제안한다. 이 방법의 핵심은 확장 계수의 2차원 배열을 특수한 이변수 생성 함수인 '계수 생성 함수'로 인코딩하는 것이다. 계수 생성 함수는 점근 확장을 간결한 폐쇄형으로 표현할 수 있는 일반적인 특성을 지닌다. 대부분의 시나리오에서 관련된 계수들의 조합론적 의미를 명확히 제시한다. 이 방법론은 연결 그래프, 기약 토너먼트, 강하게 연결된 유향 그래프, 2-SAT 공식 및 모순된 강하게 연결된 함의 유향 그래프의 점근 확장에 성공적으…
카테시안 곱 네트워크는 두 네트워크의 속성을 결합하여 새로운 네트워크를 구성하는 데 활용됩니다. 이 연구는 그래프 F의 정점 부분집합 S를 연결하는 스타이너 트리의 개념과, S-스타이너 트리의 최대 에지-분리 개수를 나타내는 일반화된 국소 에지-연결도 λ(S)를 다룹니다. 또한, 그래프 F의 k개 정점 부분집합에 대한 최소 λ(S) 값인 일반화된 k-에지-연결도 λ_k(F)를 정의합니다. 본 논문에서는 두 그래프 G와 H의 카테시안 곱인 G□H에서 λ_k(G□H)에 대한 날카로운 상한과 하한을 제시합니다. 이는 G와 H가 가진 고…
치환군 G ≤ Sym(Ω)에서, 기저(base)는 G 내에서 점별 안정자(pointwise stabiliser)가 자명한 Ω의 부분집합이며, 기저 크기 b(G)는 기저의 최소 크기입니다. b(G)=2인 경우, Burness와 Giudici는 크기 2의 기저를 엣지로 하는 G의 Saxl 그래프를 정의했습니다. 이후 Freedman은 이 개념을 b(G) ≥ 2인 모든 군으로 확장하여, b(G) 크기의 기저에 포함된 점들의 쌍을 엣지로 사용했습니다. 본 연구는 Saxl 그래프의 대안적 일반화인 Saxl 하이퍼그래프를 탐구합니다. 여기서…
네트워크 또는 그래프는 과학 분야 전반에서 다양한 관계를 표현하는 데 광범위하게 활용됩니다. igraph 소프트웨어 라이브러리(https://igraph.org)는 그래프 구축, 분석 및 시각화를 지원하며, 빠르고 견고한 성능과 낮은 진입 장벽을 결합합니다. igraph는 C로 작성된 고속 코어와 Python, R, Mathematica 등 초보자 친화적인 인터페이스를 제공합니다. 20년간의 개발 끝에 igraph 1.0이 출시되어 월간 백만 건 이상의 다운로드를 기록하며 안정적인 네트워크 분석 기능을 대중에게 제공하고 있습니다.…
