Przypuszczenie Harbortha
Czy każdy graf planarny ma integralne osadzenie Fáry'ego?
W matematyce hipoteza Harbortha stwierdza , że każdy graf planarny ma planarny rysunek , w którym każda krawędź jest odcinkiem prostym o długości całkowitej . To przypuszczenie nosi imię Heiko Harbortha i (jeśli jest prawdziwe) wzmocniłoby twierdzenie Fáry'ego o istnieniu rysunków linii prostych dla każdego wykresu planarnego. Z tego powodu rysunek z całkowitymi długościami krawędzi jest również znany jako integralne osadzanie Fáry'ego . Pomimo wielu późniejszych badań przypuszczenie Harbortha pozostaje nierozwiązane.
Specjalne klasy grafów
Chociaż hipoteza Harbortha nie jest prawdziwa dla wszystkich grafów planarnych, została udowodniona dla kilku specjalnych rodzajów grafów planarnych.
Jedną klasą grafów, które mają integralne osadzenie Fáry'ego, są grafy, które można zredukować do pustego wykresu za pomocą sekwencji operacji dwóch typów:
- Usunięcie wierzchołka stopnia co najwyżej dwa.
- Zastąpienie wierzchołka stopnia trzeciego krawędzią między dwoma jego sąsiadami. (Jeśli taka krawędź już istnieje, wierzchołek stopnia trzeciego można usunąć bez dodawania kolejnej krawędzi między jego sąsiadami).
W przypadku takiego wykresu racjonalne osadzenie Fáry'ego można konstruować stopniowo, odwracając ten proces usuwania, wykorzystując fakt, że zbiór punktów znajdujących się w racjonalnej odległości od dwóch danych punktów jest gęsty na płaszczyźnie i że jeśli trzy punkty mają wymierne odległość między jedną parą i pierwiastek kwadratowy z wymiernej odległości między dwiema pozostałymi parami, to punkty w racjonalnych odległościach od wszystkich trzech znów są gęste na płaszczyźnie. Odległości w takim osadzeniu można przekształcić w liczby całkowite, skalując osadzanie przez odpowiedni współczynnik. Opierając się na tej konstrukcji, grafy, o których wiadomo, że mają integralne osadzenie Fáry'ego, obejmują dwudzielny grafy planarne, (2,1)-rzadkie grafy planarne, grafy planarne o szerokości drzewa co najwyżej 3 i grafy o stopniu co najwyżej 4, które albo zawierają podgraf rombowy , albo nie są połączone 4-krawędziowo .
W szczególności grafy, które można zredukować do pustego wykresu przez usunięcie tylko wierzchołków stopnia co najwyżej drugiego (grafy planarne zdegenerowane 2 ), obejmują zarówno grafy planarne zewnętrzne , jak i grafy szeregowo-równoległe . Jednak w przypadku grafów płaszczyzny zewnętrznej możliwa jest bardziej bezpośrednia konstrukcja integralnych osadzeń Fáry'ego, oparta na istnieniu nieskończonych podzbiorów koła jednostkowego, w których wszystkie odległości są racjonalne.
Ponadto dla każdej z pięciu brył platońskich znane są integralne osadzenia Fáry'ego .
Powiązane przypuszczenia
Silniejsza wersja hipotezy Harbortha, postawiona przez Klebera (2008) , stawia pytanie, czy każdy graf planarny ma planarny rysunek, w którym wszystkie współrzędne wierzchołków oraz długości krawędzi są liczbami całkowitymi. Wiadomo, że jest to prawdziwe dla 3-regularnych grafów , dla grafów, które mają maksymalny stopień 4, ale nie są 4-regularne, oraz dla planarnych 3-drzew .
Inny nierozwiązany problem w geometrii, problem Erdősa-Ulama , dotyczy istnienia gęstych podzbiorów płaszczyzny, w której wszystkie odległości są liczbami wymiernymi . Gdyby taki podzbiór istniał, tworzyłby uniwersalny zbiór punktów , za pomocą którego można by rysować wszystkie grafy planarne o wymiernych długościach krawędzi (a więc po odpowiednim ich przeskalowaniu, o całkowitych długościach krawędzi). Jednak Ulam przypuszczał, że nie istnieją gęste zbiory odległości racjonalnych. Zgodnie z twierdzeniem Erdősa-Anninga , nie mogą istnieć nieskończone niewspółliniowe zbiory punktów, w których wszystkie odległości są liczbami całkowitymi. Nie wyklucza to istnienia zbiorów ze wszystkimi odległościami wymiernymi, ale oznacza, że w każdym takim zbiorze mianowniki odległości wymiernych muszą rosnąć dowolnie duże.
Zobacz też
- Trójkąt całkowity , integralne osadzenie Fáry'ego wykresu trójkątnego
- Wykres zapałek , wykres, który można narysować płasko ze wszystkimi długościami krawędzi równymi 1
- Wykres Erdősa – Diofantyny , pełny wykres z całkowitymi odległościami, których nie można rozszerzyć na większy pełny wykres o tej samej właściwości
- Cegła Eulera , problem realizacji całkowitoliczbowo-odległościowej w trzech wymiarach