Shannon capacity of a graph (original) (raw)
In graph theory, the Shannon capacity of a graph is a graph invariant defined from the number of independent sets of strong graph products. It is named after American mathematician Claude Shannon. It measures the Shannon capacity of a communications channel defined from the graph, and is upper bounded by the Lovász number, which can be computed in polynomial time. However, the computational complexity of the Shannon capacity itself remains unknown.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, the Shannon capacity of a graph is a graph invariant defined from the number of independent sets of strong graph products. It is named after American mathematician Claude Shannon. It measures the Shannon capacity of a communications channel defined from the graph, and is upper bounded by the Lovász number, which can be computed in polynomial time. However, the computational complexity of the Shannon capacity itself remains unknown. (en) Ёмкость Шеннона (шенноновская ёмкость) — характеристика неориентированного графа, описывающая предельную плотность кодирования с возможностью гарантированного отслеживания ошибок в канале связи, модель которого представляет данный граф. В этой модели вершины графа соответствуют символам алфавита, а наличие ребра между двумя вершинами означает, что при передаче первый символ может быть заменён на второй, а второй — на первый. Вероятности или частота, с которыми это происходит, в модели не рассматриваются, целью является построение оптимального способа кодирования, устойчивого к сколь угодно непредсказуемым ошибкам такого рода. Несмотря на "практичную" формулировку, задача определения шенноновской ёмкости того или иного графа на текущий момент носит сугубо теоретический характер. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Cycle_graph_C5.png?width=300 |
| dbo:wikiPageID | 39932177 (xsd:integer) |
| dbo:wikiPageLength | 12034 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1104784799 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Independence_number dbr:Independent_set_(graph_theory) dbc:Graph_invariants dbr:Ellipsoid_method dbr:Noise_(electronics) dbr:Strong_product_of_graphs dbr:Claude_Shannon dbr:Modular_arithmetic dbr:NP-hard dbr:Lovász_number dbr:Computational_complexity_theory dbr:Pentagon dbr:String_(computer_science) dbc:Information_theory dbr:Cycle_graph dbr:Field_(mathematics) dbr:Graph_theory dbr:Code_word dbr:Graph_invariant dbr:Polynomial_time dbr:Maximum_independent_set dbr:Communications_channel dbr:Shannon_capacity dbr:Strong_graph_product dbr:File:Cycle_graph_C5.png |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Not_a_typo dbt:Reflist dbt:Short_description dbt:Sqrt dbt:Unsolved |
| dcterms:subject | dbc:Graph_invariants dbc:Information_theory |
| gold:hypernym | dbr:Invariant |
| rdf:type | yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants |
| rdfs:comment | In graph theory, the Shannon capacity of a graph is a graph invariant defined from the number of independent sets of strong graph products. It is named after American mathematician Claude Shannon. It measures the Shannon capacity of a communications channel defined from the graph, and is upper bounded by the Lovász number, which can be computed in polynomial time. However, the computational complexity of the Shannon capacity itself remains unknown. (en) Ёмкость Шеннона (шенноновская ёмкость) — характеристика неориентированного графа, описывающая предельную плотность кодирования с возможностью гарантированного отслеживания ошибок в канале связи, модель которого представляет данный граф. Несмотря на "практичную" формулировку, задача определения шенноновской ёмкости того или иного графа на текущий момент носит сугубо теоретический характер. (ru) |
| rdfs:label | Shannon capacity of a graph (en) Ёмкость Шеннона (ru) |
| owl:sameAs | freebase:Shannon capacity of a graph yago-res:Shannon capacity of a graph wikidata:Shannon capacity of a graph dbpedia-ru:Shannon capacity of a graph https://global.dbpedia.org/id/fM4k |
| prov:wasDerivedFrom | wikipedia-en:Shannon_capacity_of_a_graph?oldid=1104784799&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Cycle_graph_C5.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Shannon_capacity_of_a_graph |
| is dbo:wikiPageRedirects of | dbr:Confusability_graph dbr:Confusion_graph |
| is dbo:wikiPageWikiLink of | dbr:Lovász_number dbr:Erdős–Ko–Rado_theorem dbr:Confusability_graph dbr:Confusion_graph |
| is foaf:primaryTopic of | wikipedia-en:Shannon_capacity_of_a_graph |
