Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Тек бірінші және соңғы төбелері тең болатын жол. Графтар теориясында, графтың циклі – тек бірінші және соңғы төбелері тең болатын бос емес жол. Бағытталған графтың бағытталған циклі – тек бірінші және соңғы төбелері бірдей болатын бос емес бағытталған жол. Циклдары жоқ граф ациклді граф деп аталады. Бағытталған циклдары жоқ бағытталған граф бағытталған ациклді граф деп аталады. Циклдары жоқ байланысқан граф ағаш деп аталады.
Trail in which only the first and last vertices are equal. In graph theory, a cycle in a graph is a non empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an acyclic graph. A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree.
Сұлба және цикл
Сұлба – бірінші және соңғы төбелері бірдей бос емес жол (жабық жол). 1=G = (V, E, Φ) графы болсын. Сұлба – бұл төбелер тізбегімен (v1, v2, ..., vn, v1) көрсетілген бос емес жол (e1, e2, ..., en). Цикл немесе қарапайым сұлба – тек бірінші және соңғы төбелері тең болатын сұлба. n – сұлбаның ұзындығы немесе циклдің ұзындығы.
A circuit is a non empty trail in which the first and last vertices are equal (closed trail). Let 1=G = (V, E, Φ) be a graph. A circuit is a non empty trail (e1, e2, , en) with a vertex sequence (v1, v2, , vn, v1). A cycle or simple circuit is a circuit in which only the first and last vertices are equal. n is called the length of the circuit resp. length of the cycle.
Бағытталған контур және бағытталған цикл
Бағытталған контур — бірінші және соңғы төбелері бірдей (жабық бағытталған жол) бос емес бағытталған жол. 1=G = (V, E, Φ) бағытталған граф болсын. Бағытталған контур — бұл төбелер тізбегі (v1, v2, ..., vn, v1) болатын бос емес бағытталған жол (e1, e2, ..., en). Бағытталған цикл немесе қарапайым бағытталған контур — тек бірінші және соңғы төбелері бірдей болатын бағытталған контур. n — бағытталған контурдың немесе бағытталған циклдің ұзындығы.
A directed circuit is a non empty directed trail in which the first and last vertices are equal (closed directed trail). Let 1=G = (V, E, Φ) be a directed graph. A directed circuit is a non empty directed trail (e1, e2, , en) with a vertex sequence (v1, v2, , vn, v1). A directed cycle or simple directed circuit is a directed circuit in which only the first and last vertices are equal. n is called the length of the directed circuit resp. length of the directed cycle.
Ақылды цикл
Графиктегі хордсыз цикл, сонымен қатар тесік немесе индукцияланған цикл деп аталады, – бұл циклдің екі төбесі циклге жатпайтын қабырғамен байланыспайтын цикл. Антитесік – графтың тесігінің толықтырылысы. Хордсыз циклдарды толық графиктерді сипаттау үшін пайдалануға болады: берік толық граф теоремасына сәйкес, граф толық болады, егер және тек қана оның тесіктерінің немесе антитесіктерінің үштен артық тақ саны болмаса. Хордалық граф, толық графтың ерекше түрі, үштен үлкен тесіктерге ие болмайды. Графиктің шеңбері – оның ең қысқа циклының ұзындығы; бұл цикл міндетті түрде хордсыз болады. Клеткалар – берілген дәрежелер мен шеңберлердің комбинацияларына ие ең кішкентай тұрақты графиктер. Шекаралық цикл – бұл циклдегі екі қабырға, циклге жатпаса, циклден тысқары ішкі төбелерді пайдаланбайтын жолмен байланыса алатын қасиетке ие графтың циклы. Циклға бір қабырға қосып құрылмаған графтарда шекаралық цикл индукцияланған цикл болуы керек.
A chordless cycle in a graph, also called a hole or an induced cycle, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. An antihole is the complement of a graph hole. Chordless cycles may be used to characterize perfect graphs: by the strong perfect graph theorem, a graph is perfect if and only if none of its holes or antiholes have an odd number of vertices that is greater than three. A chordal graph, a special type of perfect graph, has no holes of any size greater than three. The girth of a graph is the length of its shortest cycle; this cycle is necessarily chordless. Cages are defined as the smallest regular graphs with given combinations of degree and girth. A peripheral cycle is a cycle in a graph with the property that every two edges not on the cycle can be connected by a path whose interior vertices avoid the cycle. In a graph that is not formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle.
Цикл кеңістігі
Цикл термині график циклі кеңістігінің элементіне де қатысты болуы мүмкін. Әрбір коэффициенттік өріс немесе сақина үшін бірнеше цикл кеңістігі бар. Ең көп қолданылатыны – екілік цикл кеңістігі (көбінесе жай ғана цикл кеңістігі деп аталады), ол әр төбесінде жұп дәрежелі жиектер жиынтығынан тұрады; ол екі элементті өріс үстінде векторлық кеңістік құрайды. Веблен теоремасына сәйкес, цикл кеңістігінің кез келген элементін қарапайым циклдардың жиектерінен ажыратылған біріктірілісі ретінде құруға болады. График циклі негізі – цикл кеңістігінің негізін құрайтын қарапайым циклдар жиынтығы. Алгебралық топологиядан алынған идеяларды пайдалана отырып, екілік цикл кеңістігі басқа сақиналардағы векторлық кеңістіктерге немесе модульдерге, мысалы, бүтін сандарға, рационал немесе нақты сандарға және т.б. дейін жалпыланады.
The term cycle may also refer to an element of the cycle space of a graph. There are many cycle spaces, one for each coefficient field or ring. The most common is the binary cycle space (usually called simply the cycle space), which consists of the edge sets that have even degree at every vertex; it forms a vector space over the two element field. By Veblen's theorem, every element of the cycle space may be formed as an edge disjoint union of simple cycles. A cycle basis of the graph is a set of simple cycles that forms a basis of the cycle space. Using ideas from algebraic topology, the binary cycle space generalizes to vector spaces or modules over other rings such as the integers, rational or real numbers, etc.
Циклдерді анықтау
Бағытталған және бағытталмаған графтарда циклдың бар екені тереңдікке бірінші іздеу (DFS) арқылы ағымдағы төбесінің ата-тегіне нұсқайтын қабырғаны (яғни, кері қабырғаны) тапса анықталады. DFS өткізіп жіберген барлық кері қабырғалар циклдың бөлігі болып табылады. Бағытталмаған графтарда түйіннің ата-анасына дейінгі қабырға кері қабырға ретінде есептелмеуі керек, бірақ басқа кез келген бұрын барылған төбе табылуы кері қабырғаны көрсетеді. Бағытталмаған графтар үшін n төбесі бар графтан цикл табу үшін O(n) уақыт жеткілікті, себебі ең көп дегенде n-1 қабырға ағаш қабырғалары бола алады. Көптеген топологиялық реттеу алгоритмдері де циклдарды анықтайды, өйткені олар топологиялық реттің болуына кедергі келтіреді. Сондай-ақ, егер бағытталған граф берік байланысқан компоненттерге бөлінген болса, циклдар тек компоненттер ішінде ғана болады, олардың арасында емес, себебі циклдар берік байланысқан.
The existence of a cycle in directed and undirected graphs can be determined by whether a depth first search (DFS) finds an edge that points to an ancestor of the current vertex (i. e., it contains a back edge). All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an n vertex graph, since at most n − 1 edges can be tree edges. Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.
Цикл бойынша графиктерді қамту
1736 жылы Кенигсбергтің жеті көпірі туралы мақаласында, граф теориясының тууы деп есептелетін, Леонард Эйлер шекті бағытталмаған графтың әр қабырғасын дәл бір рет аралап өтетін жабық жолдың болуы үшін (яғни жабық траекторияның) оқшауланған төбелерді есептемегенде, графтың байланысты болуы қажет және жеткілікті екенін дәлелдеді (яғни барлық қабырғалар бір компонентке жатады) және әр төбеде жұп сан дәрежеде болуы керек. Бағытталған граф үшін әр қабырғаны дәл бір рет аралап өтетін жабық жолдың болу шарты – графтың күшті байланысты болуы және әр төбеде кіріс және шығыс қабырғаларының саны тең болуы. Екі жағдайда да алынған жабық траектория Эйлер траекториясы деп аталады. Егер шекті бағытталмаған графтың төбелері байланысқан немесе байланыспаған болуына қарамастан, әр төбесінде жұп сан дәрежеде болса, онда әр қабырғаны дәл бір рет жабатын қарапайым циклдар жиынтығын табу мүмкін: бұл Веблен теоремасы. Егер байланысты граф Эйлер теоремасының шарттарына қанағаттандырмаса, онда әр қабырғаны кем дегенде бір рет жабатын ең аз ұзындығы бар жабық жол, алайда, маршрутты тексеру мәселесін шешу арқылы полиномиалдық уақытта табылуы мүмкін. Қабырғаларды емес, төбелерді дәл бір рет аралап өтетін қарапайым цикл табу мәселесі әлдеқайда қиын. Мұндай цикл Гамильтон циклі деп аталады, оның бар-жоғын анықтау NP-толық мәселе. Гамильтон циклдерін қамтитынына кепілдік беретін графтар кластары туралы көптеген зерттеулер жарияланды; мысалы, Оре теоремасы бойынша, егер графтың кез келген жақын емес төбелер жұбының дәрежелерінің қосындысы графтың төбелерінің жалпы санынан кем болмаса, онда Гамильтон циклін табуға болады. Циклді екі есе жабу гипотезасы, кез келген көпірсіз граф үшін графтың әр қабырғасын дәл екі рет жабатын қарапайым циклдардың көп жиынтығы бар екенін айтады. Бұл гипотезаның дұрыстығын дәлелдеу (немесе қарсы мысал табу) әлі де ашық мәселе болып қалып отыр.
In his 1736 paper on the Seven Bridges of Königsberg, widely considered to be the birth of graph theory, Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once (making it a closed trail), it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex. The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be strongly connected and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting closed trail is known as an Eulerian trail. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is Veblen's theorem. When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in polynomial time by solving the route inspection problem. The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a Hamiltonian cycle, and determining whether it exists is NP complete. Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is Ore's theorem that a Hamiltonian cycle can always be found in a graph for which every non adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph. The cycle double cover conjecture states that, for every bridgeless graph, there exists a multiset of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem.