Rank (graph theory) (original) (raw)
Hodnost grafu je takové číslo, které určuje . Počet uzlů je označen a počet komponent grafu je označen . Jako důsledek definice hodnosti grafu vyplývá, že každý souvislý graf má hodnost rovnu počtu uzlů – 1.
| Property | Value |
|---|---|
| dbo:abstract | Hodnost grafu je takové číslo, které určuje . Počet uzlů je označen a počet komponent grafu je označen . Jako důsledek definice hodnosti grafu vyplývá, že každý souvislý graf má hodnost rovnu počtu uzlů – 1. (cs) In graph theory, a branch of mathematics, the rank of an undirected graph has two unrelated definitions. Let n equal the number of vertices of the graph. * In the matrix theory of graphs the rank r of an undirected graph is defined as the rank of its adjacency matrix.Analogously, the nullity of the graph is the nullity of its adjacency matrix, which equals n − r. * In the matroid theory of graphs the rank of an undirected graph is defined as the number n − c, where c is the number of connected components of the graph. Equivalently, the rank of a graph is the rank of the oriented incidence matrix associated with the graph.Analogously, the nullity of the graph is the nullity of its oriented incidence matrix, given by the formula m − n + c, where n and c are as above and m is the number of edges in the graph. The nullity is equal to the first Betti number of the graph. The sum of the rank and the nullity is the number of edges. (en) Ранг неорієнтованого графа має два не пов'язані між собою визначення. Нехай n дорівнює числу вершин графа. * У термінах теорії матриць ранг r неорієнтованого графа визначається як ранг його матриці суміжності.Аналогічно, графа визначається як дефект ядра його матриці суміжності, що дорівнює n − r. * У термінах теорії матроїдів графів ранг неорієнтованого графа визначається як число n − c, де c — число компонент зв'язності графа. Еквівалентно, ранг графа — це ранг асоційованої з ним орієнтованої матриці інцидентності.Аналогічно, графа — це дефект ядра орієнтованої матриці інцидентності, що задається формулою m − n + c, де n та c визначено вище, а m — число ребер графа. Дефект дорівнює першому числу Бетті графа. Сума рангу та дефекту дає число ребер. (uk) Ранг неориентированного графа имеет два не связанных друг с другом определения. Пусть n равно числу вершин графа. * В терминах теории матриц ранг r неориентированного графа определяется как ранг его матрицы смежности.Аналогично, графа определяется как дефект ядра его матрицы смежности, что равно n − r. * В терминах теории матроидов графов ранг неориентированного графа определяется как число n − c, где c — число связных компонент графа. Эквивалентно, ранг графа — это ранг ориентированной матрицы инцидентности, ассоциированной с графом.Аналогично, графа — это дефект ядра ориентированной матрицы инцидентности, который задаётся формулой m − n + c, где n и c определены выше, а m — число рёбер графа. Дефект равен первому числу Бетти графа. Сумма ранга и дефекта даёт число рёбер. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Labeled_undirected_graph.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.sciencedirect.com/science/article/pii/S0024379596005137/pdf%3Fmd5=d4fb4bfce95f03fecb3e51f0c4d3af0d&isDTMRedir=Y&pid=1-s2.0-S0024379596005137-main.pdf&_valck=1 |
| dbo:wikiPageID | 17458495 (xsd:integer) |
| dbo:wikiPageLength | 3332 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1047594839 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Graph_connectivity dbr:Betti_number dbr:Cycle_rank dbr:Undirected_graph dbr:Incidence_matrix dbc:Graph_invariants dbr:Nullity_(graph_theory) dbc:Algebraic_graph_theory dbr:Adjacency_matrix dbr:Graph_theory dbr:Rank_(linear_algebra) dbr:Kernel_(matrix) dbr:Circuit_rank dbr:Connected_component_(graph_theory) dbr:Vertex_(graph_theory) dbr:Matrix_theory dbr:Matroid_theory dbr:File:Labeled_undirected_graph.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Math dbt:Graph_connectivity_sidebar |
| dct:subject | dbc:Graph_connectivity dbc:Graph_invariants dbc:Algebraic_graph_theory |
| gold:hypernym | dbr:Number |
| rdf:type | yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants |
| rdfs:comment | Hodnost grafu je takové číslo, které určuje . Počet uzlů je označen a počet komponent grafu je označen . Jako důsledek definice hodnosti grafu vyplývá, že každý souvislý graf má hodnost rovnu počtu uzlů – 1. (cs) Ранг неорієнтованого графа має два не пов'язані між собою визначення. Нехай n дорівнює числу вершин графа. * У термінах теорії матриць ранг r неорієнтованого графа визначається як ранг його матриці суміжності.Аналогічно, графа визначається як дефект ядра його матриці суміжності, що дорівнює n − r. * У термінах теорії матроїдів графів ранг неорієнтованого графа визначається як число n − c, де c — число компонент зв'язності графа. Еквівалентно, ранг графа — це ранг асоційованої з ним орієнтованої матриці інцидентності.Аналогічно, графа — це дефект ядра орієнтованої матриці інцидентності, що задається формулою m − n + c, де n та c визначено вище, а m — число ребер графа. Дефект дорівнює першому числу Бетті графа. Сума рангу та дефекту дає число ребер. (uk) Ранг неориентированного графа имеет два не связанных друг с другом определения. Пусть n равно числу вершин графа. * В терминах теории матриц ранг r неориентированного графа определяется как ранг его матрицы смежности.Аналогично, графа определяется как дефект ядра его матрицы смежности, что равно n − r. * В терминах теории матроидов графов ранг неориентированного графа определяется как число n − c, где c — число связных компонент графа. Эквивалентно, ранг графа — это ранг ориентированной матрицы инцидентности, ассоциированной с графом.Аналогично, графа — это дефект ядра ориентированной матрицы инцидентности, который задаётся формулой m − n + c, где n и c определены выше, а m — число рёбер графа. Дефект равен первому числу Бетти графа. Сумма ранга и дефекта даёт число рёбер. (ru) In graph theory, a branch of mathematics, the rank of an undirected graph has two unrelated definitions. Let n equal the number of vertices of the graph. * In the matrix theory of graphs the rank r of an undirected graph is defined as the rank of its adjacency matrix.Analogously, the nullity of the graph is the nullity of its adjacency matrix, which equals n − r. * In the matroid theory of graphs the rank of an undirected graph is defined as the number n − c, where c is the number of connected components of the graph. Equivalently, the rank of a graph is the rank of the oriented incidence matrix associated with the graph.Analogously, the nullity of the graph is the nullity of its oriented incidence matrix, given by the formula m − n + c, where n and c are as above and m is the number of (en) |
| rdfs:label | Hodnost (graf) (cs) Rank (graph theory) (en) Ранг (теория графов) (ru) Ранг (теорія графів) (uk) |
| owl:sameAs | freebase:Rank (graph theory) yago-res:Rank (graph theory) wikidata:Rank (graph theory) dbpedia-cs:Rank (graph theory) dbpedia-ru:Rank (graph theory) dbpedia-uk:Rank (graph theory) https://global.dbpedia.org/id/4tVzN |
| prov:wasDerivedFrom | wikipedia-en:Rank_(graph_theory)?oldid=1047594839&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Labeled_undirected_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Rank_(graph_theory) |
| is dbo:wikiPageDisambiguates of | dbr:Rank |
| is dbo:wikiPageWikiLink of | dbr:Nullity_(graph_theory) dbr:Graph_minor dbr:Component_(graph_theory) dbr:Dual_graph dbr:Rank dbr:Tutte_polynomial dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Topology_(electrical_circuits) |
| is foaf:primaryTopic of | wikipedia-en:Rank_(graph_theory) |
