Кіріспе
Барлық нүктелері 4-дәрежелі график. Граф теориясының математикалық саласында, төртінші дәрежелі график – барлық нүктелерінің дәрежесі 4-ке тең болатын график. Басқаша айтқанда, төртінші дәрежелі график – 4-тұрақты график.
In the mathematical field of graph theory, a quartic graph is a graph where all vertices have degree 4. In other words, a quartic graph is a 4 regular graph.
Мысалдар
Көптеген белгілі графиктер төртінші дәрежелі болып табылады. Олардың ішінде: толық K5 графигі, 5 төбесі бар төртінші дәрежелі график, мүмкін болатын ең кішкентай төртінші дәрежелі график. Chvátal графигі, тағы бір 12 төбесі бар төртінші дәрежелі график, үшбұрыштары жоқ және үш түспен боялмайтын ең кішкентай төртінші дәрежелі график. Фолькман графигі, 20 төбесі бар төртінші дәрежелі график, ең кішкентай жартылай симметриялық график. Мередит графигі, 70 төбесі бар, 4-байланысқан, бірақ Гамильтон циклы жоқ төртінші дәрежелі график, Криспин Нэш Уильямстың болжамын жоққа шығарады. Кез келген медиалдық график - төртінші дәрежелі жазық график, ал кез келген төртінші дәрежелі жазық график - екі жазық график немесе көпграфтар жұбының медиалдық графигі. Түйін диаграммалары мен байланыс диаграммалары да төртінші дәрежелі жазық көпграфтар болып табылады, онда төбелер диаграмманың қиылыс нүктелерін көрсетеді және түйіннің екі тармағының қайсысы сол нүктеде екінші тармақты кесіп өтетіні туралы қосымша ақпаратпен белгіленеді.
The complete graph K5, a quartic graph with 5 vertices, the smallest possible quartic graph. The Chvátal graph, another quartic graph with 12 vertices, the smallest quartic graph that both has no triangles and cannot be colored with three colors. The Folkman graph, a quartic graph with 20 vertices, the smallest semi symmetric graph. The Meredith graph, a quartic graph with 70 vertices that is 4 connected but has no Hamiltonian cycle, disproving a conjecture of Crispin Nash Williams. Every medial graph is a quartic plane graph, and every quartic plane graph is the medial graph of a pair of dual plane graphs or multigraphs. Knot diagrams and link diagrams are also quartic plane multigraphs, in which the vertices represent the crossings of the diagram and are marked with additional information concerning which of the two branches of the knot crosses the other branch at that point.
Қасиеттері
Квартиктік графиктегі әрбір төбесінің дәрежесі жұп болғандықтан, әрбір байланысқан квартиктік графиктің Эйлер айналымы болады. Жалпы, реттелген екібөлікті графиктердегідей, әрбір екібөлікті квартиктік графиктің толық сәйкестігі болады. Бұл жағдайда, мұндай сәйкестікті табу үшін, ретсіз графиктерге қарағанда әлдеқайда қарапайым және жылдам алгоритм қолдануға болады: Эйлер айналымының кез келген екінші қабырғасын таңдау арқылы 2-фактор табуға болады, ол осы жағдайда циклдар жиынтығы болуы керек, олардың әрқайсысы жұп ұзындықта, ал графиктің әрбір төбесі дәл бір циклде кездеседі. Осы циклдардағы кез келген екінші қабырғаны қайта таңдау арқылы сызықтық уақытта толық сәйкестікке қол жеткізіледі. Осы әдіс графиктің қабырғаларын сызықтық уақытта төрт түспен бояу үшін де қолданылуы мүмкін. Квартиктік графиктерде Гамильтон ыдырауларының жұп саны болады.
Ашық мәселелер
Барлық төртінші дәрежелі Гамильтондық графтардың Гамильтондық циклдарының саны жұп бола ма, немесе бірнен артық Гамильтондық циклдары бола ма деген мәселе әлі шешілмеген. Бірақ төртінші дәрежелі көпграфтар үшін бұл жаңсақ екені белгілі.