Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Граф теориясында кітап граф (көбінесе жазылады) – бір жиекті бөлісетін бірнеше циклдан құралған графтың әр түрлі түрі болуы мүмкін.
In graph theory, a book graph (often written ) may be any of several kinds of graph formed by multiple cycles sharing an edge.
Вариациялар
Төртбұрышты кітап деп аталатын бір түрі, жалпы қабырғаны бөлісетін (кітаптың "тірегі" немесе "негізі" деп аталатын) p төртбұрыштан тұрады. Яғни, бұл жұлдыз бен жалғыз қабырғаның декарт көбейтіндісі. Осы типтегі 7 беттік кітап графигі үйлесімді белгілеуі жоқ графтың мысалы болып табылады. Осы типтегі кітап – бөлінген граф. Бұл граф тагомизер графигі деп те аталады (тагомизерлер – стегозавр динозаврларының тікенекті құйрықтары, кейбір суреттердегі өткір пішініне байланысты) және олардың графикалық матроидтары тагомизер матроидтары деп аталады. Үшбұрышты кітаптар сызықтық толық графтардың негізгі құраушы бөліктерінің бірі болып табылады. "Кітап графигі" термині басқа мақсаттарда да қолданылған. Бариоли оны екі ортақ төбесі бар кез келген қосалқы графтардан тұратын графты білдіру үшін пайдаланған. (Бариоли өзінің кітап графигі үшін жазба жасаған жоқ.)
One kind, which may be called a quadrilateral book, consists of p quadrilaterals sharing a common edge (known as the "spine" or "base" of the book). That is, it is a Cartesian product of a star and a single edge. The 7 page book graph of this type provides an example of a graph with no harmonious labeling. A book of this type is a split graph. This graph has also been called a or a thagomizer graph (after thagomizers, the spiked tails of stegosaurian dinosaurs, because of their pointy appearance in certain drawings) and their graphic matroids have been called thagomizer matroids. Triangular books form one of the key building blocks of line perfect graphs. The term "book graph" has been employed for other uses. Barioli used it to mean a graph composed of a number of arbitrary subgraphs having two vertices in common. (Barioli did not write for his book graph.)
Үлкен графтар ішінде
Берілген граф бойынша, оның ішіндегі қарастырылып жатқан түрдегі ең үлкен кітапты жазуға болады.
Given a graph , one may write for the largest book (of the kind being considered) contained within .
Кітаптардағы теоремалар
Екі үшбұрышты кітаптың Рамси санын деп белгілейміз. Бұл кез келген төбелік граф үшін, графтың өзінде немесе оның толықтыру графында төбелік үшбұрыш субграф ретінде кездесетін ең кіші сан. Егер , онда тұрақты бар, егер және үлкен болса, Рамси саны формуласымен беріледі. деген тұрақтыны қарастырайық, онда төбесі және қабырғасы бар кез келген граф (үшбұрышты) үшбұрыш субграфына ие болады.
Denote the Ramsey number of two triangular books by This is the smallest number such that for every vertex graph, either the graph itself contains as a subgraph, or its complement graph contains as a subgraph. If , then There exists a constant such that whenever If , and is large, the Ramsey number is given by Let be a constant, and Then every graph on vertices and edges contains a (triangular) .