Түйіндер: Графтардың негізгі құрамы

Кіріспе

Графтар құрылатын негізгі бірлік. Дискретті математикада, әсіресе граф теориясында, төбе (көпше түбелер) немесе түйін – графтар құрылатын негізгі бірлік: бағытталмаған граф төбелер мен қабырғалар жиынтығынан (ретсіз жұп түбелер), ал бағытталған граф төбелер мен доғалар жиынтығынан (реттелген жұп түбелер) тұрады. Графтың схемасында, төбе әдетте белгісі бар шеңбермен бейнеленеді, ал қабырға бір төбеден екіншісіне созылатын сызық немесе жебемен бейнеленеді. Граф теориясы тұрғысынан алғанда, төбелер ерекшеліксіз және бөлінбейтін нысандар ретінде қарастырылады, бірақ олар графтың пайда болуына байланысты қосымша құрылымға ие болуы мүмкін; мысалы, семантикалық желі – бұл төбелер түсініктерді немесе нысандардың кластарын көрсететін граф. Қабырғаны құрайтын екі төбе осы қабырғаның соңғы нүктелері деп аталады, ал қабырға төбелерге жанасады. w төбесі, егер графта (v,w) қабырғасы болса, басқа v төбесімен іргелес деп аталады. v төбесінің көршілесі – v төбесіне іргелес барлық төбелерден құралған графтың индукцияланған кіші графы.

Қиыршықтардың түрлері

Графикте 𝛿(v) деп белгіленетін төбе дәрежесі – оған жанасқан қабырғалардың саны. Оқшауланған төбе – нөлдік дәрежелі төбе; яғни, ешқандай қабырғаның соңғы нүктесі емес төбе (мысал суретте бір оқшауланған төбе көрсетілген). Жапырақ төбе (сондай-ақ, ілгек төбе) – бірінші дәрежелі төбе. Бағытталған графикте шығу дәрежесін (шығу қабырғаларының саны), 𝛿+(v) деп белгіленетін, кіру дәрежесінен (кіру қабырғаларының саны), 𝛿−(v) деп белгіленетін, ажыратуға болады; бастапқы төбе – нөлдік кіру дәрежесі бар төбе, ал аяқтаушы төбе – нөлдік шығу дәрежесі бар төбе. Симплициалды төбе – оның көршілері клика құрайды: кез келген екі көршісі іргелес. Универсалды төбе – графтың барлық төбелеріне іргелес төбе. Кесілетін төбе – оны алып тастау қалған графикті үзуге әкелетін төбе; төбелерді бөлуші – оны алып тастау қалған графикті кішкентай бөліктерге үзуге әкелетін төбелер жиыны. k-төбелі байланысты граф – k-дан кем төбелерді алып тастау қалған графикті әрқашан байланысты қалдыратын граф. Тәуелсіз жиын – ешқайсысы іргелес емес төбелер жиыны, ал төбелерді жабатын жиын – графтың әр қабырғасының кем дегенде бір соңғы нүктесін қамтитын төбелер жиыны. Графтың төбелік кеңістігі – графтың төбелеріне сәйкес келетін базистік векторлар жиыны бар векторлық кеңістік. Граф төбелік транзитивті болады, егер ол кез келген төбені кез келген басқа төбеге бейнелейтін симметрияларға ие болса. Графты санау және графтық изоморфизм контекстінде таңбаланған және таңбаланбаған төбелерді ажырату маңызды. Таңбаланған төбе – басқа таңбаланған төбелерден ажыратуға мүмкіндік беретін қосымша ақпаратпен байланысты төбе; екі граф тек олардың төбелері арасындағы сәйкестік тең таңбалары бар төбелерді жұптаса ғана изоморфты деп есептеледі. Таңбаланбаған төбе – оның графтың ішіндегі іргелес орналасуына ғана негізделген және қосымша ақпаратқа негізделмеген кез келген басқа төбеге ауыстырылуы мүмкін төбе. Графтағы төбелер полиэдрлердің төбелеріне ұқсас, бірақ олармен бірдей емес: полиэдрдің қаңқасы графты құрайды, оның төбелері полиэдрдің төбелері болып табылады, бірақ полиэдрдің төбелері қосымша құрылымға ие (олардың геометриялық орналасуы), граф теориясында олардың болуы қабылданбайды. Полиэдрдің төбесінің төбелік фигурасы – графтың төбесінің көршілігіне ұқсас.

The degree of a vertex, denoted 𝛿(v) in a graph is the number of edges incident to it. An isolated vertex is a vertex with degree zero; that is, a vertex that is not an endpoint of any edge (the example image illustrates one isolated vertex). A leaf vertex (also pendant vertex) is a vertex with degree one. In a directed graph, one can distinguish the outdegree (number of outgoing edges), denoted 𝛿 +(v), from the indegree (number of incoming edges), denoted 𝛿−(v); a source vertex is a vertex with indegree zero, while a sink vertex is a vertex with outdegree zero. A simplicial vertex is one whose neighbors form a clique: every two neighbors are adjacent. A universal vertex is a vertex that is adjacent to every other vertex in the graph. A cut vertex is a vertex the removal of which would disconnect the remaining graph; a vertex separator is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. A k vertex connected graph is a graph in which removing fewer than k vertices always leaves the remaining graph connected. An independent set is a set of vertices no two of which are adjacent, and a vertex cover is a set of vertices that includes at least one endpoint of each edge in the graph. The vertex space of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices. A graph is vertex transitive if it has symmetries that map any vertex to any other vertex. In the context of graph enumeration and graph isomorphism it is important to distinguish between labeled vertices and unlabeled vertices. A labeled vertex is a vertex that is associated with extra information that enables it to be distinguished from other labeled vertices; two graphs can be considered isomorphic only if the correspondence between their vertices pairs up vertices with equal labels. An unlabeled vertex is one that can be substituted for any other vertex based only on its adjacencies in the graph and not based on any additional information. Vertices in graphs are analogous to, but not the same as, vertices of polyhedra: the skeleton of a polyhedron forms a graph, the vertices of which are the vertices of the polyhedron, but polyhedron vertices have additional structure (their geometric location) that is not assumed to be present in graph theory. The vertex figure of a vertex in a polyhedron is analogous to the neighborhood of a vertex in a graph.