Кіріспе
График теориясы
graph theory
Граф теориясының математикалық саласында, жиектік транзитивті граф – бұл G графындағы кез келген екі жиек пен үшін, осы жиекті жиекке бейнелейтін G-нің автоморфизмі бар граф. Басқаша айтқанда, граф жиектері бойынша транзитивті әрекет ететін автоморфизм тобына ие болса, онда ол жиектік транзитивті граф болып саналады.
In other words, a graph is edge transitive if its automorphism group acts transitively on its edges.
Мысалдар мен қасиеттері
n төбесі бар жалғасқан қарапайым жиектік транзитивті графтардың саны 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28-ге тең. Жиектік транзитивті графтар барлық симметриялық графтарды қамтиды, мысалы, кубтың төбелері мен жиектері. Жиектері бойынша, бірақ төбелері бойынша емес, транзитивті графтардың мысалдары m ≠ n болғандағы толық екі бөлікті графтарды қамтиды, оларға жұлдыз тәрізді графтар да кіреді. n төбесі бар графтар үшін, тақ n үшін (n-1)/2, ал жұп n үшін (n-2) осындай графтар бар. Кейбір жағдайларда симметриялық емес, қосымша жиектік транзитивті графтар осы толық екі бөлікті графтардың кіші графтары ретінде құрылуы мүмкін. m және n ортақ бөлгіші 2-ден үлкен болғанда, Km,n толық екі бөлікті графтарының кіші графтары бар. Ең үлкен ортақ бөлгіш 2 болғанда, 2n/m жұп сан болса немесе m=4 және n 6-ның тақ еселігі болса, кіші графтар бар. Осылайша, K3,6, K4,6 және K5,10 үшін жиектік транзитивті кіші графтар бар, бірақ K4,10 үшін жоқ. Кейбір жиектік транзитивті графтарды құрудың басқа жолы – v төбесі және e жиегі бар симметриялық графтың жиектерінің орталық нүктелеріне төбелер қосу, нәтижесінде 2 реті бар e төбесі және v реті бар 2e/v төбесі бар екі бөлікті граф құрылады. Жиектік транзитивті, бірақ төбелік транзитивті емес, тұрақты граф жартылай симметриялық деп аталады. 54 төбесі бар кубикалық граф – Грей графигі, жиектік транзитивті, бірақ төбелік транзитивті емес тұрақты графтың мысалы. 20 төбесі бар квартикалық граф – Фолькман графигі, мұндай графтардың ең кішісі. Жиектік транзитивті графтың төбелік байланысы әрқашан оның ең төменгі дәрежесіне тең.
Edge transitive graphs include all symmetric graph, such as the vertices and edges of the cube. Examples of edge but not vertex transitive graphs include the complete bipartite graphs where m ≠ n, which includes the star graphs For graphs on n vertices, there are (n 1)/2 such graphs for odd n and (n 2) for even n.
Additional edge transitive graphs which are not symmetric can be formed as subgraphs of these complete bi partite graphs in certain cases. Subgraphs of complete bipartite graphs Km,n exist when m and n share a factor greater than 2. When the greatest common factor is 2, subgraphs exist when 2n/m is even or if m=4 and n is an odd multiple of 6. So edge transitive subgraphs exist for K3,6, K4,6 and K5,10 but not K4,10. An alternative construction for some edge transitive graphs is to add vertices to the midpoints of edges of a symmetric graph with v vertices and e edges, creating a bipartite graph with e vertices of order 2, and v of order 2e/v. An edge transitive graph that is also regular, but still not vertex transitive, is called semi symmetric. The Gray graph, a cubic graph on 54 vertices, is an example of a regular graph which is edge transitive but not vertex transitive. The Folkman graph, a quartic graph on 20 vertices is the smallest such graph. The vertex connectivity of an edge transitive graph always equals its minimum degree.