Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Комбинаторлық математикада Леви графигі немесе инциденттік графигі – инциденттік құрылыммен байланысты екіжақты граф. Инциденттік геометриядағы немесе проективтік конфигурациядағы нүктелер мен түзулер жиынтығынан, әр нүктеге бір төбе, әр түзуге бір төбе және нүкте мен түзудің кездесуіне сәйкес жиектері бар граф құрастырылады. Олар 1942 жылы олар туралы жазған Фридрих Вильгельм Левидің құрметіне аталған. Нүктелер мен түзулер жүйесінің Леви графигінің ұзындығы кем дегенде алтыға тең: кез келген 4 цикл бірдей екі нүкте арқылы өтетін екі түзуге сәйкес келеді. Керісінше, ұзындығы кем дегенде алты болатын кез келген екіжақты графты абстрактілік инциденттік құрылымның Леви графигі ретінде қарастыруға болады. Леви графтары Евклид кеңістігіндегі нүктелер мен жазықтықтар арасындағы кездесулер сияқты, басқа да инциденттік құрылым түрлері үшін де анықталуы мүмкін. Кез келген Леви графигі үшін эквивалентті гиперграф бар, және керісінше.
In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure. From a collection of points and lines in an incidence geometry or a projective configuration, we form a graph with one vertex per point, one vertex per line, and an edge for every incidence between a point and a line. They are named for Friedrich Wilhelm Levi, who wrote about them in 1942. The Levi graph of a system of points and lines usually has girth at least six: Any 4 cycles would correspond to two lines through the same two points. Conversely any bipartite graph with girth at least six can be viewed as the Levi graph of an abstract incidence structure. Levi graphs may also be defined for other types of incidence structure, such as the incidences between points and planes in Euclidean space. For every Levi graph, there is an equivalent hypergraph, and vice versa.
Мысалдар
Десарг графигі – Десарг конфигурациясының Леви графигі, 10 нүкте мен 10 сызықтан тұрады. Әр сызықта 3 нүкте бар, әр нүктеден өтетін 3 сызық бар. Десарг графигін жалпыланған Петерсен графигі G(10,3) немесе 5,2 параметрлері бар екіжақты Кнезер графигі ретінде де қарастыруға болады. Ол 3-ретті және 20 төбесі бар. Хевуд графигі – Фано жазықтығының Леви графигі. Ол (3,6) тор деп те аталады, 3-ретті және 14 төбесі бар. Мёбиус-Кантор графигі – Мёбиус-Кантор конфигурациясының Леви графигі, 8 нүкте мен 8 сызықтан тұратын жүйе, оны Евклид жазықтығында түзу сызықтармен жүзеге асыруға болмайды. Ол 3-ретті және 16 төбесі бар. Паппус графигі – 9 нүкте мен 9 сызықтан тұратын Паппус конфигурациясының Леви графигі. Десарг конфигурациясындағыдай, әр сызықта 3 нүкте бар және әр нүктеден өтетін 3 сызық бар. Ол 3-ретті және 18 төбесі бар. Грей графигі – 27 нүктеден тұратын тор және олар арқылы өтетін 27 ортогональды сызықтар түрінде жүзеге асырылатын конфигурацияның Леви графигі. Тютте сегіздік торы – Кремона-Ричмонд конфигурациясының Леви графигі. Ол (3,8) торы деп те аталады және 3-ретті, 30 төбесі бар. Төрт өлшемді гиперкуб графигі – екі өзара келісетін тетраэдрлердің нүктелері мен жазықтықтарынан құралған Мёбиус конфигурациясының Леви графигі. 112 төбесі бар Любляна графигі – Любляна конфигурациясының Леви графигі.
The Desargues graph is the Levi graph of the Desargues configuration, composed of 10 points and 10 lines. There are 3 points on each line, and 3 lines passing through each point. The Desargues graph can also be viewed as the generalized Petersen graph G(10,3) or the bipartite Kneser graph with parameters 5,2. It is 3 regular with 20 vertices. The Heawood graph is the Levi graph of the Fano plane. It is also known as the (3,6) cage, and is 3 regular with 14 vertices. The Möbius–Kantor graph is the Levi graph of the Möbius–Kantor configuration, a system of 8 points and 8 lines that cannot be realized by straight lines in the Euclidean plane. It is 3 regular with 16 vertices. The Pappus graph is the Levi graph of the Pappus configuration, composed of 9 points and 9 lines. Like the Desargues configuration there are 3 points on each line and 3 lines passing through each point. It is 3 regular with 18 vertices. The Gray graph is the Levi graph of a configuration that can be realized in as a grid of 27 points and the 27 orthogonal lines through them. The Tutte eight cage is the Levi graph of the Cremona–Richmond configuration. It is also known as the (3,8) cage, and is 3 regular with 30 vertices. The four dimensional hypercube graph is the Levi graph of the Möbius configuration formed by the points and planes of two mutually incident tetrahedra. The Ljubljana graph on 112 vertices is the Levi graph of the Ljubljana configuration.