Circuit rank (original) (raw)
Cyklomatické číslo grafu je minimální počet hran takový, že po jejich odstranění nebude v grafu žádný cyklus. Cyklomatické číslo C(G) značí počet nezávislých kružnic v grafu. Pokud C(G) = 0, tak graf neobsahuje kružnice. Obecně pro každý graf existuje cyklomatické číslo, pro které platí:C(G) = E – N + P Cyklomatické číslo je také rovno počtu tětiv. Tětivy jsou ty hrany, které zbudou potom, co se odebere minimální kostra grafu.
| Property | Value |
|---|---|
| dbo:abstract | Cyklomatické číslo grafu je minimální počet hran takový, že po jejich odstranění nebude v grafu žádný cyklus. Cyklomatické číslo C(G) značí počet nezávislých kružnic v grafu. Pokud C(G) = 0, tak graf neobsahuje kružnice. Obecně pro každý graf existuje cyklomatické číslo, pro které platí:C(G) = E – N + P Cyklomatické číslo je také rovno počtu tětiv. Tětivy jsou ty hrany, které zbudou potom, co se odebere minimální kostra grafu. (cs) Die zyklomatische Zahl ist ein Begriff aus dem mathematischen Teilgebiet der Graphentheorie. (de) La cirkvita rango de grafeo G estas la minimuma kvanto m de lateroj kiuj necesas forpreni por ke la grafeo estu sencikla. Ĝi povas esti kalkulita kiel r = m - n + c kie m estas la kvanto de lateroj en G n estas la kvanto de verticoj en Gc estas la kvanto de de G Arbo kaj arbaro havas cirkvitan rangon 0. (eo) In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph (the size of a cycle basis). Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula , where m is the number of edges in the given graph, n is the number of vertices, and c is the number of connected components. It is also possible to construct a minimum-size set of edges that breaks all cycles efficiently, either using a greedy algorithm or by complementing a spanning forest. The circuit rank can be explained in terms of algebraic graph theory as the dimension of the cycle space of a graph, in terms of matroid theory as the corank of a graphic matroid, and in terms of topology as one of the Betti numbers of a topological space derived from the graph. It counts the ears in an ear decomposition of the graph, forms the basis of parameterized complexity on almost-trees, and has been applied in software metrics as part of the definition of cyclomatic complexity of a piece of code. Under the name of cyclomatic number, the concept was introduced by Gustav Kirchhoff. (en) Liczba cyklomatyczna - minimalna liczba krawędzi potrzebna do usunięcia w nieskierowanym grafie G, taka, żeby usunąć wszystkie cykle w grafie G (równoważnie - żeby graf G stał się lasem). (pl) В теории графов контурный ранг неориентированного графа — это минимальное число рёбер, удаление которых разрушает все циклы графа, превращая его в дерево или лес. Контурный ранг можно понимать также как число независимых циклов в графе. В отличие от соответствующей задачи нахождения для ориентированных графов, контурный ранг r легко вычисляется по формуле , где m — число рёбер заданного графа, n — число вершин, а c — число компонент связности. Можно также эффективно построить множество рёбер минимального размера, разбивающих циклы, используя либо жадный алгоритм, либо дополнение остовного дерева. Контурный ранг известен также как цикломатическое число графа. Его можно объяснить в терминах алгебраической теории графов как размерность циклического пространства графа, в терминах матроидов с использованием понятия коранга и в терминах топологии как одно из чисел Бетти топологического пространства, производного от графа. Контурный ранг подсчитывает число ушей в ушной декомпозиции графа, что даёт базис для понятия на почти деревьях и применяется в метриках программного обеспечения как часть определения цикломатической сложности фрагмента кода. Под названием цикломатическая сложность понятие было введено Густавом Кирхгофом. (ru) Цикломати́чне число́ або ко́нтурний ранг — ізоморфна характеристика графів. Для графу L, цикломатичне число λ(L) дорівнює: , де * m(L) — кількість ребер, * n(L) — кількість його вершин, * — кількість компонент. Основні властивості цикломатичного числа: * λ(L) ≥ 0; * λ(L) = 0 тоді і тільки тоді, коли граф не містить циклів; * при λ(L) > 0 на L можна видалити λ(L) ребер таким чином, щоб суграф, який залишиться не мав циклів і мав попередню кількість компонент; будь-який суграф, отриманий із L видаленням меншої кількості ребер, містить цикли. Будь-який суграф T, який задовольняє умови * , * m(T) = m(L) − λ(L), * λ(T) = 0, називається каркасом графу L, а видалені ребра хордами L (відносно T). Кожна компонента каркаса є деревом, яке містить всі вершини відповідної компоненти графу L. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/6n-graf.svg?width=300 |
| dbo:wikiPageID | 1483049 (xsd:integer) |
| dbo:wikiPageLength | 13446 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1093606518 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Software_metric dbr:Meshedness_coefficient dbr:Algebraic_graph_theory dbc:Matroid_theory dbc:Spanning_tree dbr:Homology_theory dbr:Betti_number dbr:Perfect_matching dbr:Cycle_(graph_theory) dbr:Cycle_basis dbr:Cycle_rank dbr:Cycle_space dbr:Undirected_graph dbr:Ear_decomposition dbr:Line_segment dbr:Pseudoforest dbc:Graph_invariants dbr:Complement_(set_theory) dbr:Mathematics dbr:Maximal_planar_graph dbr:Cheminformatics dbr:NP-hard dbr:Feedback_arc_set dbr:Feedback_vertex_set dbr:Matching_preclusion dbr:Matroid_rank dbr:Topology dbr:Tree_(graph_theory) dbr:K-vertex-connected_graph dbr:Cyclomatic_complexity dbr:Directed_graph dbr:Graph_theory dbr:Graphic_matroid dbr:Simplicial_complex dbr:Tree-depth dbr:Rank_of_an_abelian_group dbr:Ring_(chemistry) dbr:Gustav_Kirchhoff dbr:Chemistry dbr:Planar_graph dbr:Connected_component_(graph_theory) dbr:Greedy_algorithm dbr:Vertex_(graph_theory) dbr:Symmetric_difference dbr:Spanning_forest dbr:Molecular_graph dbr:Topological_space dbr:Parameterized_complexity dbr:Smallest_set_of_smallest_rings dbr:Matroid_theory dbr:Edge_connectivity dbr:Homology_group dbr:File:6n-graf.svg |
| dbp:wikiPageUsesTemplate | dbt:For dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Matroid_theory dbc:Spanning_tree dbc:Graph_invariants |
| rdf:type | yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants |
| rdfs:comment | Cyklomatické číslo grafu je minimální počet hran takový, že po jejich odstranění nebude v grafu žádný cyklus. Cyklomatické číslo C(G) značí počet nezávislých kružnic v grafu. Pokud C(G) = 0, tak graf neobsahuje kružnice. Obecně pro každý graf existuje cyklomatické číslo, pro které platí:C(G) = E – N + P Cyklomatické číslo je také rovno počtu tětiv. Tětivy jsou ty hrany, které zbudou potom, co se odebere minimální kostra grafu. (cs) Die zyklomatische Zahl ist ein Begriff aus dem mathematischen Teilgebiet der Graphentheorie. (de) La cirkvita rango de grafeo G estas la minimuma kvanto m de lateroj kiuj necesas forpreni por ke la grafeo estu sencikla. Ĝi povas esti kalkulita kiel r = m - n + c kie m estas la kvanto de lateroj en G n estas la kvanto de verticoj en Gc estas la kvanto de de G Arbo kaj arbaro havas cirkvitan rangon 0. (eo) Liczba cyklomatyczna - minimalna liczba krawędzi potrzebna do usunięcia w nieskierowanym grafie G, taka, żeby usunąć wszystkie cykle w grafie G (równoważnie - żeby graf G stał się lasem). (pl) In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph (the size of a cycle basis). Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula , (en) В теории графов контурный ранг неориентированного графа — это минимальное число рёбер, удаление которых разрушает все циклы графа, превращая его в дерево или лес. Контурный ранг можно понимать также как число независимых циклов в графе. В отличие от соответствующей задачи нахождения для ориентированных графов, контурный ранг r легко вычисляется по формуле , (ru) Цикломати́чне число́ або ко́нтурний ранг — ізоморфна характеристика графів. Для графу L, цикломатичне число λ(L) дорівнює: , де * m(L) — кількість ребер, * n(L) — кількість його вершин, * — кількість компонент. Основні властивості цикломатичного числа: * λ(L) ≥ 0; * λ(L) = 0 тоді і тільки тоді, коли граф не містить циклів; * при λ(L) > 0 на L можна видалити λ(L) ребер таким чином, щоб суграф, який залишиться не мав циклів і мав попередню кількість компонент; будь-який суграф, отриманий із L видаленням меншої кількості ребер, містить цикли. Будь-який суграф T, який задовольняє умови (uk) |
| rdfs:label | Cyklomatické číslo (graf) (cs) Zyklomatische Zahl (de) Cirkvita rango (eo) Circuit rank (en) Liczba cyklomatryczna (pl) Контурный ранг (ru) Цикломатичне число (uk) |
| owl:sameAs | freebase:Circuit rank yago-res:Circuit rank wikidata:Circuit rank dbpedia-cs:Circuit rank dbpedia-de:Circuit rank dbpedia-eo:Circuit rank dbpedia-hu:Circuit rank dbpedia-pl:Circuit rank dbpedia-ru:Circuit rank dbpedia-sk:Circuit rank dbpedia-sr:Circuit rank dbpedia-uk:Circuit rank https://global.dbpedia.org/id/4hnW4 |
| prov:wasDerivedFrom | wikipedia-en:Circuit_rank?oldid=1093606518&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/6n-graf.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Circuit_rank |
| is dbo:wikiPageRedirects of | dbr:Circuit_Rank dbr:Frerejacque_number dbr:Frèrejacque_number dbr:Cyclomatic_Number dbr:Cyclomatic_number |
| is dbo:wikiPageWikiLink of | dbr:Mac_Lane's_planarity_criterion dbr:Meshedness_coefficient dbr:Bicircular_matroid dbr:Cycle_basis dbr:Cycle_rank dbr:Cycle_space dbr:Ear_decomposition dbr:Nullity_(graph_theory) dbr:Glossary_of_graph_theory dbr:Corank dbr:Component_(graph_theory) dbr:Feedback_arc_set dbr:Feedback_vertex_set dbr:Frère_Jacques dbr:Halin_graph dbr:Matroid_rank dbr:Peripheral_cycle dbr:GNRS_conjecture dbr:Circuit_Rank dbr:Dual_graph dbr:Graph_property dbr:Graphic_matroid dbr:Rank_(graph_theory) dbr:Gustav_Kirchhoff dbr:Planar_graph dbr:Ihara_zeta_function dbr:Frerejacque_number dbr:Frèrejacque_number dbr:Cyclomatic_Number dbr:Cyclomatic_number |
| is foaf:primaryTopic of | wikipedia-en:Circuit_rank |
