Графтардың абстрактілі құрылымына тәуелді қасиеттері
Graph property
Графтардың абстракт құрылымына байланысты қасиеттері: график инварианттары, изоморфизмдерге қарамастан сақталатын, сандық және сипаттамалық түрдегі қасиеттер.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Графтардың абстрактілі құрылымына ғана тәуелді қасиеттері
Property of graphs that depends only on abstract structure
Графтар теориясында графтың қасиеті немесе граф инварианты – графтардың абстрактілі құрылымына ғана тәуелді, ал графтың нақты белгіленуі немесе сызбасы сияқты бейнелеулеріне тәуелді емес қасиеті болып табылады.
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.
Анықтамалар
Графтарды сызу және графтарды бейнелеу – граф теориясындағы қолданылатын тақырыптар болғанымен, графтардың абстрактілі құрылысына назар аудару мақсатында, графтың қасиеті – графтың барлық мүмкін изоморфизмінде сақталатын қасиет ретінде анықталады. Яғни, бұл графтың өзіне тән қасиеті, оның нақты сызылысына немесе бейнесіне байланысты емес. Көбінесе, сандық тұрғыда берілген қасиеттер үшін "граф инварианты" термині қолданылады, ал "қасиет" әдетте графтардың сипаттамалық белгілеріне жатады. Мысалы, "графта 1-дәрежелі төбелер жоқ" дегені – "қасиет", ал "графтағы 1-дәрежелі төбелер саны" – "инвариант". Күрделірек айтқанда, графтың қасиеті – егер екі граф изоморф болса, олардың екеуі де осы қасиетке ие болады немесе екеуі де ие болмайды.
While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph. Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant". More formally, a graph property is a class of graphs with the property that any two isomorphic graphs either both belong to the class, or both do not belong to it.
Граф инварианттары мен графикалық изоморфизмдер
Жеңіл есептелетін граф инварианттары граф изоморфизмін жылдам анықтау үшін өте маңызды, немесе дәлірек айтқанда, изоморфизм емес екенін анықтау үшін, себебі кез келген инвариант бойынша екі графтың мәндері әртүрлі болса, олар (анықтама бойынша) изоморфты бола алмайды. Бірақ, егер екі графтың инварианттары бірдей болса, олар изоморфты болуы да, болмауы да мүмкін. Егер I(G) және I(H) инварианттарының теңдігі G және H графтарының изоморфизмін білдірсе, онда I(G) инварианты толық деп аталады. Мұндай инвариантты тиімді есептеу (графты канонизациялау мәселесі) қиын граф изоморфизмі мәселесін оңай шешуге мүмкіндік береді. Дегенмен, тіпті хроматикалық полином сияқты полиномдық мәнді инварианттар да көбінесе толық болмайды. Мысалы, тырнақ граф және 4 төбелі жол графтың екеуінің де хроматикалық полиномы бірдей.
Easily computable graph invariants are instrumental for fast recognition of graph isomorphism, or rather non isomorphism, since for any invariant at all, two graphs with different values cannot (by definition) be isomorphic. Two graphs with the same invariants may or may not be isomorphic, however. A graph invariant I(G) is called complete if the identity of the invariants I(G) and I(H) implies the isomorphism of the graphs G and H. Finding an efficiently computable such invariant (the problem of graph canonization) would imply an easy solution to the challenging graph isomorphism problem. However, even polynomial valued invariants such as the chromatic polynomial are not usually complete. The claw graph and the path graph on 4 vertices both have the same chromatic polynomial, for example.