단어 표시 그래프

그래프 이론의 수학적 분야에서 단어 표현 가능한 그래프는 단어(또는 시퀀스)로 특징지어질 수 있는 그래프로서, 입력 내용이 규정된 방식으로 번갈아 나타난다.특히 그래프의 꼭지점 집합이 V인 경우, 알파벳 V를 넘어 a와 b가 번갈아 가며, 쌍 ab가 그래프의 엣지일 경우에만. (a와 b는, a와 b의 사본을 제외한 모든 문자에서 제거한 후, a와 b가 단어 abababab을 얻으면 w를 교대하도록 선택할 수 있어야 한다...또는 단어 baba....) 예를 들어 시계방향으로 a, b, c, d로 표기한 주기 그래프는 abdacdbc: ab, bc, cd, ad 대체로 나타낼 수 있지만 ac와 bd 쌍은 그렇지 않기 때문에 단어를 나타낼 수 있다.

w라는 단어는 G의 단어로, w는 G를 나타낸다고 한다.가장 작은(정점 수 기준) 비단어 표기가 가능한 그래프는 휠 그래프 W로₅, 6개의 정점에 있는 유일한 비단어 표기가 된다.

단어 표현 가능한 그래프의 정의는 그래프의 어떤 라벨 표시도 다른 라벨 표시와 동일하기 때문에 라벨 표시와 라벨 표시되지 않은 사례 모두에서 작동한다.또한, 단어 표현 가능한 그래프의 등급은 유전적이다.단어 표현 가능한 그래프는 원 그래프, 3색 그래프, 비교가능성 그래프와 같은 몇 가지 중요한 등급의 그래프를 일반화한다.단어 표현 가능한 그래프 이론의 다양한 일반화는 어떤 그래프의 표현을 수용한다.

역사

단어 표현형 그래프는 세르게이 키타예프가 퍼킨스 세미그룹에 대한 스티븐 세이프와의^[1] 공동 연구를 바탕으로 2004년 도입해 1960년부터 세미그룹 이론에 중요한 역할을 해왔다.^[2]단어표현 가능한 그래프의 첫 번째 체계적 연구는 키타예프와 아르템 파이트킨이 2008년 논문에서 진행되어 ^[3]이론의 개발을 시작했다.이 지역의 주요 공헌자 중 한 명이 마그누스 M이다. 할도르손.^[4][5][6]현재까지 이 주제에 대해 35편 이상의 논문이 작성되었으며, 세르게이 키타예프, 바딤 로진 등이^[2] 쓴 책의 핵심은 단어표현 가능한 그래프 이론에 전념하고 있다.그 지역에 익숙해지는 빠른 방법은 조사 기사 중 하나를 읽는 것이다.^[7][8][9]

그래프를 연구하는 동기

이에 따르면 단어표현형 그래프는 다양한 분야와 관련이 있어 그래프를 연구하는 동기를 부여한다.^[2]이 분야들은 대수학, 그래프 이론, 컴퓨터 과학, 단어에 대한 조합학, 스케줄링이다.단어 표현형 그래프는 원 그래프, 3색 그래프 및 비교가능성 그래프와 같은 몇 가지 중요한 등급의 그래프를 일반화하기 때문에 그래프 이론에서 특히 중요하다.

초기 결과

그래프 G가 일부 k에 대해 k-표현 가능하다면, 즉 G는 각 글자의 k-복사를 가진 단어로 표현될 수 있다는 것을 알 수 있다.더욱이, 그래프가 k-표현가능하면 (k + 1)표현가능하다.따라서 그래프가 단어를 나타낼 수 있는 최소 k인 그래프의 표현 번호 개념은 잘 정의되어 있다.비단어표현 그래프에는 표현번호 ∞이 있다. 표현번호 1을 가진 그래프는 정확히 완전한 그래프의 집합인 반면, 표현번호 2를 가진 그래프는 정확히 원이 아닌 완전하지 않은 그래프의 분류인 것이다.특히 숲(대부분 2정점에 있는 단일 트리는 제외), 사다리 그래프 및 사이클 그래프는 2번 표현을 가지고 있다.표현 번호가 3인 그래프의 분류는 알려져 있지 않다.그러나 피터슨의 그래프와 프리즘과 같은 그러한 그래프의 예가 있다.또한 어떤 그래프의 3분할도 3분할 수 있다.특히 모든 그래프 G에 대해 G를 마이너로 포함하는 3개의 대표 그래프 H가 존재한다.^[3]

그래프 G는 pp₁₂...p_k 형식의 단어로 나타낼 수 있다면 순열적으로 표현할 수 있다. 여기서 p는_i 순열이다.온은 또한 G가 순전적으로 k-표현이 가능하다고 말할 수 있다.그래프는 비교가능성 그래프일 경우 순리적으로 표현할 수 있다.^[1]그래프는 단어를 나타낼 수 있으며 각 꼭지점의 인접성이 순리적으로 표현 가능하다는 것을 암시한다(즉, 비교가능성 그래프).^[1]마지막 진술에 대한 반론은 사실이 아니다.^[4]그러나 각 꼭지점의 인접성이 비교가능성 그래프라는 사실은 최대 클라이크 문제가 단어 표현 가능한 그래프에서 다항적으로 해결 가능하다는 것을 암시한다.^[5][6]

반투명 방향

반역전향은 단어표현이 가능한 그래프를 연구하는 강력한 도구를 제공한다.지시된 그래프는 반역학적으로 만약 그것이 반복된다면 그리고 어떤 지시된 경로에 대해서도 u₁→u₂→...→u_t, t ≥ 2, u에서₁ u까지의_t 엣지가 없거나 u_i → u가_j 1 i i < j t t. 단어표현 가능한 그래프 이론의 핵심 정리는 그래프가 반역적 방향을 인정하는 경우 단어표현이 가능하다고 기술하고 있다.^[6]핵심 정리 증명에 대한 귀결로서, 단어 대표자에게 상한을 구한다.각 비완전 단어표현 그래프 G는 2(n - κ(G)-표현가능하며, 여기서 κ(G)는 G에서 최대 패거리의 크기.^[6] 마지막 문장의 즉각적인 귀결로서 단어표현성의 인식 문제가 NP에 있음을 알 수 있다.2014년에 Vincent Limouzy는 주어진 그래프가 단어를 나타낼 수 있는지 여부를 인식하는 것은 NP-완전한 문제라고 관찰했다.^[2][7]핵심 정리의 또 다른 중요한 귀결점은 3색 그래프는 단어를 표현할 수 있다는 것이다.마지막 사실은 많은 고전적인 그래프 문제들이 단어를 표현할 수 있는 그래프에서 NP-hard라는 것을 암시한다.

선택한 결과 개요

단어를 나타낼 수 없는 그래프

휠 그래프 W는_2n+1 n graphs 2에 대해 단어를 나타낼 수 없으며 W는₅ 단어를 나타낼 수 없는 최소 그래프(정점 수 기준)이다.비교가능성이 없는 그래프를 가져다가 꼭지점(다른 꼭지점에 연결된 꼭지점)을 추가하면, 우리는 비단어표현 가능한 그래프를 얻을 수 있고, 그 그래프는 무한히 많은 비단어표현 가능한 그래프를 생산할 수 있다.^[2]이러한 방식으로 생성된 그래프는 반드시 삼각형(길이 3의 주기)과 최소 5도 정도의 꼭지점이 있어야 한다.최대 4도의 비단어 표기가 가능한 그래프가 존재하며 비단어 표기가 없는 삼각형 자유 그래프가 존재한다.^[5]일반적인 비단어 표현 가능한 그래프도 존재한다.^[2]Heman Z.Q는 최대 8개의 꼭지점에 있는 비이등형 비단어 표기가 가능한 연결 그래프를 먼저 열거했다.Chen. 그의 계산이 확장되었는데,^[11] 여기서 5-11 정점에 있는 비 이형성 비단어 표기가 가능한 연결 그래프의 수는 각각 0, 1, 25, 929, 54957, 4880093, 650856040으로 나타났다.온라인 정수 백과사전(OEIS)의 A290814 시퀀스다.

그래프 및 단어 표현성에 대한 연산

단어 표현성을 보존하는 작업은 정점을 제거하고 정점을 모듈로 대체하며, 데카르트 제품, 뿌리 제품, 그래프의 하위 분할, 두 개의 그래프를 가장자리로 연결하고 정점에 두 개의 그래프를 붙이는 것이다.^[2]단어 표현성을 반드시 보존하지 않는 작업은 선 그래프, 모서리 수축,^[2] 2개 이상의 크기,^[12] 텐서 제품, 사전 편찬 제품 및 강력한 제품으로 구성된 두 개의 그래프를 붙이는 작업으로 보완을 취하고 있다.^[13]단어 표현 가능성(동등, 반투명 방향성)에 관한 에지 삭제, 에지 추가 및 에지 리프팅이 연구된다.^[13]

표현 번호가 높은 그래프

각 비완전한 단어 표시 그래프 G는 2(n - κ(G)-표현 가능한 반면, 여기서 κ(G)는 G에서 최대 클라이크의 크기인 반면,^[6] 가장 높은 알려진 표현 번호는 모든 인접 정점을 가진 크라운 그래프에 의해 주어지는 바닥(n/2)이다.^[6]흥미롭게도, 그러한 그래프만이 긴 표현을 필요로 하는 유일한 그래프는 아니다.^[14]크라운 그래프 자체는 초당적 그래프 중에서 긴(아마도 가장 긴) 표현을 필요로 하는 것으로 나타났다.^[15]

계산 복잡성

단어 표현 가능한 그래프의 문제에 대한 알려진 계산 복잡성은 다음과 같이 요약할 수 있다.^[2][7]

문제	복잡성
단어의 결정성.	NP-완전
커닝 세트	NP-하드
클라이크 커버링	NP-하드
최대 독립 집합	NP-하드
최대 클라이크	P에
ε > 0에 대한 요인 n 내의1−ε 그래프 표현 번호 근사	NP-하드

평면 그래프의 표시

삼각형이 없는 평면 그래프는 단어로 표현할 수 있다.^[6]K4-프리 근삼각형은 단어를 표현할 수 있는 경우에만 3-색상이 가능하다.^[16] 이 결과는 연구를 일반화한다.^[17][18]삼각 격자 그래프의 얼굴 부분 단어의 표현성을 연구하며 격자 덮개로 덮인 실린더 그래프의 삼각형 단어의 표현성을 연구한다.^[20]

분할 그래프 표시

분할 그래프의 단어 표기는 에서 연구된다.^[21][12]특히,^[21] 독립된 집합의 정점이 최대 2 정도인 단어 표시 가능 분할 그래프의 금지 유도 하위 그래프 또는 클릭 크기가 4인 반면, 크기 5의 클릭을 가진 단어 표시 가능 분할 그래프의 계산적 특성화가 제공된다.^[12]반면[12]문턱에서 그래프word-representable 지는 것 또한 분할식 그래프semi-transitive 한 방향에 대한 필요 충분 조건과 분열 그래프가 크기의 어떤 집단에 속해 두word-representable 그래프 붙이면 적어도 2, 또는word-representable graph,을 야기시키지 모름을 보여 주기 위해 사용된다 in,[21]이 주어진다.는오랫동안 지속되어 온 열린 문제를 해결하다

단어 회피 패턴으로 표시할 수 있는 그래프

그래프는 패턴 p를 회피하는 단어로 표현될 수 있다면 p-표현이 가능하다.예를 들어, 132개의 표현 가능한 그래프는 ww₁₂...라는 단어로 표현될 수 있는 그래프들이다.w_na w < w_c > w_b < w >와 같이 1 ≤ a < b < c ≤ n이 없는 경우.이 그림에서 132-표현 가능한 그래프는 반드시 원 그래프이며, 모든 트리 및 사이클 그래프는 최대 5-표현에 있는 그래프를 포함하여 132-표현 그래프임을 알 수 있다.모든 원 그래프가 132로 대표되는 것은 아니며, 123으로 대표되는 그래프도 원 그래프 클래스의 적절한 하위 클래스라는 것을 알 수 있었다.

일반화

단어 표현 가능한 그래프의 개념에 대한 여러 가지 일반화는 제프 렘멜이 관찰한 바에 따르면 비에지(non-edge)는 그래프를 나타내는 단어의 패턴 11(2 연속 등문자)의 발생에 의해 정의되는 반면, 가장자리는 이러한 패턴을 피하여 정의된다.예를 들어 패턴 11 대신 패턴 112, 즉 패턴 1212, 또는 알파벳 순서에 따른 가정을 할 수 있는 다른 이진 패턴을 사용하여 패턴의 1에 해당하는 단어의 문자가 패턴의 2에 해당하는 문자보다 작도록 할 수 있다.따라서 우리는 당신이 순서가 정해진 이진 패턴이 되도록 내버려두면 우리는 대표할 수 있는 그래프의 개념을 얻게 된다.그래서 단어표현형 그래프는 단지 11개의 그래프 종류일 뿐이다.흥미롭게도, 어떤 그래프도 길이가 적어도 3이라고 가정할 때 유표현될 수 있다.^[27]

제프 렘멜이 다시 제안한 단어 표현 가능한 그래프의 개념을 일반화하는 또 다른 방법은 가장자리/비 에지를 정의하는 패턴 p의 발생에 대한 "공차도" k를 도입하는 것이다.즉, 문자 a와 b에 의해 형성된 p가 k까지 발생한다면, a와 b 사이에 엣지가 있다고 말할 수 있다.이것은 k-p-표현 가능한 그래프의 개념을 제공하며, k-11표현 가능한 그래프는 에서 연구된다.^[28]0-11을 나타내는 그래프는 정확히 단어를 나타낼 수 있는 그래프라는 점에 유의하십시오.주요 결과는 어떤 그래프가 2-11을 나타낼 수 있고 단어-표현 가능한 그래프가 1-11을 나타낼 수 있는 그래프의 적절한 하위 클래스라는 것이다.그래프가 1-11로 표현 가능한지 아닌지는 어려운 개방형 문제다.

그러나 또 다른 유형의 관련 일반화에 대해 한스 잔테마는 반역적 지향의 개념을 다듬는 k-세미 변환 지향의 개념을 제안했다.^[14]여기서의 생각은 더 긴 경로에 대한 반투명의 위반을 허용하면서 k를 초과하지 않는 길의 방향 경로만을 고려하도록 우리 자신을 제한하고 있다.

문제 열기

단어 표현 가능한 그래프에서 개방형 문제를 찾을 수 있으며,^[2][7][8][9] 여기에는 다음이 포함된다.

• 단어 표현 가능한 평면 그래프를 특성화하십시오.
• 완전한 그래프 K를₄ 포함하는 단어 표현 가능한 거의 삼각형(K-free₄ planar graphs) 특성화.
• 그래프를 표시 번호 3으로 분류하십시오(이 방향의 최신 정보는 참조).
• 비단어표현 그래프의 선 그래프는 항상 비단어표현인가?
• 각 글자의 바닥(n/2) 복사본 이상의 표현을 필요로 하는 n 꼭지점에 그래프가 있는가?
• 모든 초당적 그래프 중에서 크라운 그래프가 가장 긴 단어 대표자를 필요로 한다는 것이 사실인가?(관련 논의를 위해 참조)
• 금지된 하위 그래프의 관점에서 단어 표현 가능한 그래프를 특성화한다.
• 그래프의 어떤 (힘든) 문제들이 그것들을 대표하는 단어로 번역되어 단어로 풀릴 수 있는가(효율적으로)?

문학

단어별 그래프의 표현을 연구할 수 있는 출판물 목록에는 다음이 포함되지만 이에 국한되지는 않는다.

1. ö. 악귄, I.P. 젠트, S. 기타에프, H. 잔테마.단어 표현 가능한 그래프 이론에서 계산 문제 해결.Journal of Integer Sequence 22 (2019), 제19.2.5조.
2. P. 아크로보투, S. 키타예프, Z.마사로바폴리오미노 삼각형의 단어 표현 가능성.시베리안 어드바이드.수학. 25 (2015), 1-10.
3. B. 브로레.단어 표현 가능한 그래프, 2018.Nijmegen Radboud 대학의 석사 논문.
4. B. 브로레와 H. 잔테마."k-큐브는 k-표현이 가능하다" J 오토모트, 랭, 콤빈. 24 (2019) 1, 3-12.
5. J. N. Chen과 S. Kitaev.그리드 그래프의 유도 하위 그래프의 12개 대표성에 대해, 수학 그래프 이론 논의, 표시
6. T. Z. Q. Chen, S. Kitaev, A.사이토. 단어로 분할 그래프를 나타냄, arXiv:1909.09471
7. T. Z. Q. Chen, S. Kitaev, B. Y. Sun.삼각 격자 그래프, 그래프 및 콤빈의 얼굴 부분 표현. 32(5) (2016), 1749-1761.
8. T. Z. Q. Chen, S. Kitaev, B. Y. Sun.격자로 덮인 실린더 그래프의 삼각형 그래프, Discr의 단어 표현성.답안. 수학. 213 (2016), 60-70.
9. 지에스천, 제이킴, 엠킴, 에스 키타예프.Toeplitz 그래프의 단어 표현성, Discr.'응용법' 수학, 나타나기.
10. 지에스천, 제이킴, 엠킴, A.팻킨.k-11을 나타내는 그래프에.J. 콤빈. 10 (2019) 3, 491-513.
11. I. Choi, J. Kim, M. Kim.그래프의 반투명적 방향 능력을 보존하는 작업에 대해, Journal of Combinatorial Optimization 37 (2019) 4, 1351-1366.
12. A. 콜린스, S. 키타예프, 브이 로진.단어를 나타낼 수 있는 그래프에 대한 새로운 결과, Discr.답안. 수학. 216 (2017), 136-141.
13. A. Daigavane, M. Singh, B.K. George. 2 통일된 단어: 사이클 그래프와 그래프의 특정 단어 표현을 검증하는 알고리즘. arXiv:1806.04673 (2018)
14. M. 개츠와 C.Ji. 단어 표현 가능한 그래프의 열거 및 확장.컴퓨터 과학 11682 (2019) 180-192 강의 노트R. Mercas, D.에서.리덴바흐 (Eds) 단어 위의 콤비네이터ics.WORDS 2019.
15. M. 개츠와 C.Ji. 단어 대표자의 열거 및 확장, arXiv:1909.00019.
16. M. 개츠와 C.Ji. 단어 대표자의 열거 및 확장, 단어에 대한 콤비네이터틱스, 180-192, 강의 노트 in Compute.Sci, 11682, Springer, Cham, 2019.
17. A. 가오, S. 키타예프, P. 장.132개의 그래프에 표시됨.호주 J. 콤빈. 69 (2017), 105-118.
18. M. 글렌.2019년에 등장할 거의 삼변수인 순수 및 응용 수학의 색상 및 단어 표현성.
19. M. 글렌.폴리오미노 삼각측량 & 크라운 그래프의 단어 표현 가능성에 대해, 2019년.Strathclyde 대학의 박사 논문.
20. M. Glen과 S. Kitaev.단일 Domino 타일을 사용하는 직사각형 폴리오미노 삼각형의 단어 표현성, J. 콤빈.수학. 콤빈.계산하다.100, 131−144, 2017.
21. M. Glen, S. Kitaev, A.팻킨.크라운 그래프의 표시 번호에 디스크르.답안. 수학. 244, 2018, 89-93
22. M.M. Halldorsson, S. Kitaev, A.Pyatkin On 표현 가능한 그래프, 반투명 방향 및 표현 번호 arXiv:0810.0310(2008)을 참조하십시오.
23. M.M. Halldorsson, S. Kitaev, A.Pyatkin (2010) 단어에서 교체를 캡처하는 그래프.인: Y. Gao, H. Lu, S. Seki, S. Yu(eds), Development in Language 이론.DLT 2010.강의 노트 컴프.과학 6224 스프링거 436-437
24. M.M. Halldorsson, S. Kitaev, A.Pyatkin(2011) 교류 그래프.인: P. Kolman, J. Kratochvil (eds), Graph-Teological Concepts in Computer Science.WG 2011.강의 노트 컴프.과학 6986, 스프링거 191-202
25. M. Halldorsson, S. Kitaev와 A.팻킨.반투명 방향 및 단어 표현 가능한 그래프, Discr.답안. 수학 201호(2016), 164-171.
26. M. Jones, S. Kitaev, A.파이트킨, 그리고 J. 렘멜.패턴을 통해 그래프를 나타내며 단어 회피, 전자.J. 콤빈. 22(2), 레즈. P2.53, 1-20(2015)
27. S. 기타에프.표현 번호 3, J. Automat, Lang. 및 Combin. 18(2013), 97-112의 그래프.
28. S. 기타에프.단어 표현 가능한 그래프 이론에 대한 포괄적인 소개.In: EE. Charlier, J. Leroy, M. Rigo(eds), Development in Language 이론.DLT 2017.강의 노트 컴프.과학 10396, 스프링거 36-67
29. S. 기타에프.그래프의 u-표현의 존재, 그래프 이론 85 (2017) 3, 661-668.
30. S. 기타에프, Y. 롱, J. 마, H. 우. 분할 그래프의 단어 표현성, arXiv:1709.09725(2017).
31. S. 키타예프와 V. 로진.Words and Graphs, Springer, 2015. ISBN978-319-25859-1
32. S. 기타에프와 A.팻킨.대표 가능한 그래프에서 J. Autom, Lang. 및 Combin. 13(2008), 45-54.
33. S. 기타에프와 A.팻킨.단어 표현 가능한 그래프: Survey, Journal of Application and Industrial Math 12(2)(2018) 278-296.
34. S. 기타에프와 A.팻킨.삼각형이 없는 그래프의 반투명 방향성에 대해 arXiv:2003.06204v1.
35. S. 기타에프와 A.사이토. Kneser 그래프의 반전사적 방향성과 그 보완물인 이산 수학이 나타날 것이다.
36. S. 기타에프, P. 살리모프, C.Severs, and H. Ulfarsson(2011) 선 그래프의 대표성에 대하여.인: G. Mauri, ALeborati (eds), 언어 이론의 발전.DLT 2011.강의 노트 컴프.과학 6795, 스프링거 478-479
37. S. 기타에프와 S.Seif. Perkins semigroup의 단어 문제는 지시된 반복 그래프인 Order 25(2008), 177-194를 통한 것이다.
38. E. 르루프.그래프는 다시 인쇄할 수 있다.리에주대학교 석사논문
39. 만델슈탐.패턴을 회피하는 단어로 표현 가능한 그래프에서, 토론 수학 그래프 이론 39 (2019) 375-389.
40. С. В. Китаев, А. В. Пяткин.Графы, представимые в виде слов.Обзор результатов, Дискретн.анализ и исслед.опер., 2018, том 25,номер 2, 19−53.

소프트웨어

단어 표현 가능한 그래프를 연구하는 소프트웨어는 여기에서 찾을 수 있다.

1. M. 글렌.단어 표현 가능한 그래프를 다루는 소프트웨어, 2017.https://personal.cis.strath.ac.uk/sergey.kitaev/word-representable-graphs.html에서 이용 가능.
2. H. 잔테마.그래프 표현 번호, 2018을 계산하는 소프트웨어 RPRNR.https://www.win.tue.nl/~zantema/reprnr.properties에서 이용 가능.

참조