Қайта құру туралы болжам - Reconstruction conjecture

Математикадағы шешілмеген мәселе: Графиктер олардың ішкі графиктерімен ерекше анықталған ба? (математикадағы шешілмеген мәселелер)

Бейресми түрде қайта құру гипотезасы жылы графтар теориясы графиктер өздерінің ішкі графиктерімен ерекше түрде анықталады дейді. Бұл байланысты Келли^[1] және Улам.^[2][3]

Ресми мәлімдемелер

Бір сызықпен жойылған ішкі графиктердің графигі және онымен байланысты палуба. Кейбір карталарда изоморфтық графиктер көрсетілгенін ескеріңіз.

График берілген ${ displaystyle G = (V, E)}$, а шыңдармен жойылған субография туралы ${ displaystyle G}$ Бұл подограф бастап дәл бір шыңды жою арқылы құрылған ${ displaystyle G}$. Анықтама бойынша бұл индукцияланған субография туралы ${ displaystyle G}$.

График үшін ${ displaystyle G}$, G палубасы, деп белгіленді ${ displaystyle D (G)}$, болып табылады мультисет изоморфизм кластарының барлық шыңдары жойылған субграфтардың ${ displaystyle G}$. Әрбір график ${ displaystyle D (G)}$ а деп аталады карта. Палубалары бірдей екі график деп аталады гипоморфты.

Осы анықтамалармен болжамды былай деп айтуға болады:

• Қайта құру туралы болжам: Кем дегенде үш төбенің кез-келген екі гипоморфты графигі изоморфты.

(Графиктердің кемінде үш шыңы болуы керек деген талап, өйткені екі шыңдағы екі графаның да палубалары бірдей).

Харари^[4] болжамның мықты нұсқасын ұсынды:

• Қайта құру болжамын белгілеңіз: Кем дегенде төрт шыңдағы кез-келген екі график, бірдей шыңдармен жойылған субографтардың жиынтығы изоморфты.

График берілген ${ displaystyle G = (V, E)}$, an шетінен өшірілген субография туралы ${ displaystyle G}$ Бұл подограф бастап дәл бір шетін жою арқылы пайда болды ${ displaystyle G}$.

График үшін ${ displaystyle G}$, G жиегінің палубасы, деп белгіленді ${ displaystyle ED (G)}$, болып табылады мультисет барлық изоморфизм кластарының ішінен жойылған субграфтардың ${ displaystyle G}$. Әрбір график ${ displaystyle ED (G)}$ деп аталады шеткі карта.

• Жиектерді қайта құру туралы болжам: (Харари, 1964)^[4] Кем дегенде төрт шеті бар және бірдей жиек палубалары бар кез-келген екі графика изоморфты.

Танылатын қасиеттер

Қайта құру болжамына сәйкес, а график қасиеті аталады танылатын егер графиктің палубасынан қасиетін анықтай алса. Графиктердің келесі қасиеттері танымал:

• Графиктің тәртібі - Графиктің реті ${ displaystyle G}$, ${ displaystyle | V (G) |}$ танылады ${ displaystyle D (G)}$ мультисет ретінде ${ displaystyle D (G)}$ ішіндегі әрбір ішкі графикадан тұрады ${ displaystyle G}$ бір шыңын жою арқылы жасалған ${ displaystyle G}$. Демек ${ displaystyle | V (G) | = | D (G) |}$ ^[5]
• Графиктің шеттерінің саны - Графиктегі жиектер саны ${ displaystyle G}$ бірге ${ displaystyle n}$ шыңдар, ${ displaystyle | E (G) |}$ танылады. Біріншіден, әр шеті ${ displaystyle G}$ пайда болады ${ displaystyle n-2}$ мүшелері ${ displaystyle D (G)}$. Бұл анықтамасы бойынша дұрыс ${ displaystyle D (G)}$ бұл әр шыңның әр мүшенің құрамына кірген сайын қосылуын қамтамасыз етеді ${ displaystyle D (G)}$, сондықтан әрбір мүшеде жиек болады ${ displaystyle D (G)}$ оның соңғы нүктелері жойылатын екеуін қоспағанда. Демек, ${ displaystyle | E (G) | = sum { frac {q_ {i}} {n-2}}}$ қайда ${ displaystyle q_ {i}}$ - бұл жиектер саны менмүшесі ${ displaystyle D (G)}$.^[5]
• Дәреженің реттілігі - Графиктің дәрежелік реттілігі ${ displaystyle G}$ танылады, өйткені әрбір шыңның дәрежесі танылады. Шыңның дәрежесін табу үшін ${ displaystyle v_ {i}}$- жоқ шың менмүшесі ${ displaystyle D (G)}$-, біз оны жою арқылы құрылған графиканы қарастырамыз, ${ displaystyle G_ {i}}$. Бұл графикте сәйкес келмейтін барлық шеттер бар ${ displaystyle v_ {i}}$сондықтан, егер ${ displaystyle q_ {i}}$ - шеттерінің саны ${ displaystyle G_ {i}}$, содан кейін ${ displaystyle | E (G) | -q_ {i} = deg (v_ {i})}$. Егер графиктегі әр шыңның дәрежесін айта алсақ, графиктің дәрежелік ретін айта аламыз.^[5]
• (Vertex-) қосылым - Анықтама бойынша график ${ displaystyle n}$- кез-келген шыңды өшіргенде вертикске байланысты а жасайды ${ displaystyle n-1}$-текске қосылған график; осылайша, егер әрбір карта а ${ displaystyle n-1}$-vertex-ге байланысты граф, біз бастапқы графиктің болғанын білеміз ${ displaystyle n}$-текске қосылған. Сондай-ақ, бастапқы графиктің қосылғанын анықтай аламыз, өйткені бұл кез-келген екеуіне тең ${ displaystyle G_ {i}}$ байланыстырылған.^[5]
• Тутте көпмүшесі
• Көпмүшелік
• Жоспарлылық
• Түрлері ағаштар графикте
• Хроматикалық көпмүше
• Болу а тамаша график немесе ан аралық график, немесе басқа графиктердің басқа да тамаша графиктері^[6]

Тексеру

Қайта құру және қайта құру болжамдары ең көп дегенде 11 шыңы бар барлық графиктер үшін тексерілді Брендан Маккей.^[7]

Ықтималдық мағынада оны көрсетті Бела Боллобас графиктердің барлығы дерлік қалпына келтірілетіні.^[8] Бұл кездейсоқ таңдалған графиктің ықтималдығы дегенді білдіреді ${ displaystyle n}$ шыңдар қалпына келтірілмейді, 0 мәніне ауысады ${ displaystyle n}$ шексіздікке жетеді. Шын мәнінде, графиктердің барлығы дерлік қалпына келтірілетіні ғана емес, сонымен бірге оларды палубаның барлық бөлігі қайта құрудың қажеті жоқ екендігі көрсетілді - барлық графиктердің графикасында графиканы ерекше анықтайтын үш карточка бар қасиеті бар.

Қалпына келтірілетін графтар отбасы

Болжам бірнеше графиктердің шексіз кластары үшін расталды (және олардың қосымшалары).

• Тұрақты графиктер^[9] - Тұрақты графиктер графиктің палубасынан тануға болатын кейбір фактілерді тікелей қолдану арқылы қалпына келтіріледі. Берілген ${ displaystyle n}$- тұрақты график ${ displaystyle G}$ және оның палубасы ${ displaystyle D (G)}$, палуба оның графикалық дәрежесі екенін оның дәрежесінің реттілігін тану арқылы біле аламыз. Енді палубаның бір мүшесін қарастырайық ${ displaystyle D (G)}$, ${ displaystyle G_ {i}}$. Бұл графикте дәрежесі бар шыңдардың кейбір саны бар ${ displaystyle n}$ және ${ displaystyle n}$ дәрежесі бар шыңдар ${ displaystyle n-1}$. Біз бұл графикке шың қосып, содан кейін оны байланыстыра аламыз ${ displaystyle n}$ дәреже шыңдары ${ displaystyle n-1}$ жасау ${ displaystyle n}$- біз бастаған графикке изоморфты болатын тұрақты график. Сондықтан барлық тұрақты графиктер палубаларынан қалпына келтіріледі. Кәдімгі графиктің ерекше түрі - бұл толық граф.^[5]
• Ағаштар^[9]
• Ажыратылған графиктер^[9]
• Бірлік аралық графиктер ^[6]
• Бөлінетін графиктер жоқ шыңдар^[10]
• Максималды жоспарлы графиктер
• Сыртқы жоспарлы максималды графиктер
• Сыртқы жоспарлар
• Маңызды блоктар

Қысқарту

Қайта құру гипотезасы, егер барлық 2 қосылған графиктер қалпына келтірілетін болса, дұрыс болады. ^[11]

Дуальность

Шыңды қайта құру туралы болжам екіұдайлыққа бағынады, егер болса ${ displaystyle G}$ оны шыңнан жасалған палубадан қалпына келтіруге болады ${ displaystyle D (G)}$, содан кейін оны толықтырады ${ displaystyle G '}$ бастап қалпына келтіруге болады ${ displaystyle D (G ')}$ келесідей: бастаңыз ${ displaystyle D (G ')}$алу үшін ондағы барлық карточкалардың жиынтығын алыңыз ${ displaystyle D (G)}$, мұны қалпына келтіру үшін қолданыңыз ${ displaystyle G}$, содан кейін алу үшін қайтадан комплементті алыңыз ${ displaystyle G '}$.

Жиектерді қайта құру мұндай екі жақтылыққа бағынбайды: Шынында да, кейбір жиектер бойынша қалпына келтірілетін графиктер кластары үшін олардың толықтырғыштары шеттерімен қалпына келтірілетіндігі белгісіз.

Басқа құрылымдар

Төмендегілер көрсетілген емес жалпы қалпына келтірілетін:

• Диграфтар: Қайта қалпына келтірілмейтін диграфтардың шексіз отбасылары белгілі, оның ішінде турнирлер (Стокмейер^[12]) және турнирден тыс (Стокмейер)^[13]). Турнир қатты байланыста болмаса, қалпына келтіріледі.^[14] Қайта құру болжамының әлсіз нұсқасы диграфтар үшін болжалды, қараңыз диграфты қайта құрудың жаңа болжамы.
• Гиперографтар (Kocay^[15]).
• Шексіз графиктер. Т әр шыңның шексіз дәрежесі болатындай шексіз шыңдардағы ағаш болсын және болсын nT болуы бірлескен одақ туралы n көшірмелері Т. Бұл графиктер гипоморфты, сондықтан қалпына келтірілмейді. Осы графиктердің кез-келген шыңы жойылған субграфиясы изоморфты: олардың барлығы шексіз Т көшірмелерінің бірігуі болып табылады.
• Жергілікті ақырлы графиктер. Жергілікті ақырлы шексіз ағаштарды қалпына келтіру мүмкіндігі туралы сұрақ (1972 жылғы Харари-Швенк-Скотт гипотезасы) 2017 жылға дейін ұзаққа созылған ашық мәселе болды, ол 3 дәрежелі қалпына келтірілмейтін ағашты Bowler et al.^[16]

Сондай-ақ қараңыз

• Диграфты қайта құрудың жаңа болжамы
• Жартылай симметрия

Әрі қарай оқу

Осы тақырып бойынша қосымша ақпарат алу үшін сауалнаманы қараңыз Нэш-Уильямс.^[17]

Әдебиеттер тізімі