This HTML5 document contains 65 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
template-jahttp://ja.dbpedia.org/resource/Template:
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n14http://www.cs.colostate.edu/~rmm/
n5http://www.graphclasses.org/classes/
dbpedia-wikidatahttp://wikidata.dbpedia.org/resource/
n21http://www.mscand.dk/article/view/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n6http://www.graphclasses.org/
n10http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n4http://ja.dbpedia.org/resource/Category:
wikipedia-jahttp://ja.wikipedia.org/wiki/
n16http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n12http://ja.dbpedia.org/resource/ファイル:
n7http://www.cis.uoguelph.ca/~sawada/papers/
dbpedia-jahttp://ja.dbpedia.org/resource/
prop-jahttp://ja.dbpedia.org/property/

Statements

Subject Item
dbpedia-wikidata:Q1322892
owl:sameAs
dbpedia-ja:弦グラフ
Subject Item
dbpedia-ja:弦グラフ
rdfs:label
弦グラフ
rdfs:comment
弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てが弦を持つようなグラフである。ここで、弦とは、閉路を構成しないが、閉路の2頂点をつなぐ辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である（4頂点以上の誘導グラフは閉路を持たないか、弦を持つ）。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、という頂点の順序付けが可能である」「最小頂点分離(minimal separator)（グラフを全域グラフでなくするために除去する必要最小限なグラフ）がクリークである」「木の部分木の」といった特徴も持つ。また、rigid circuit graphsや、triangulated graphとも呼ばれる。 弦グラフは完全グラフの部分グラフである。弦グラフを多項式時間で発見できることもあり、グラフ彩色のようなグラフ一般に対しては困難な問題も、弦グラフに対しては多項式時間で解ける場合もある。グラフの(treewidth)は、それを含む弦グラフのクリークのサイズによって特徴づけられるかも知れない。
dct:subject
n4:グラフ理論 n4:数学に関する記事
dbo:wikiPageID
3911826
dbo:wikiPageRevisionID
79839481
dbo:wikiPageWikiLink
n4:数学に関する記事 dbpedia-ja:外平面グラフ n4:グラフ理論 dbpedia-ja:閉路 dbpedia-ja:Perfect_elimination_ordering dbpedia-ja:K-木 dbpedia-ja:Lexicographic_Breadth_First_Search dbpedia-ja:Journal_of_Graph_Theory dbpedia-ja:International_Colloquium_on_Automata,_Languages_and_Programming n12:Chordal-graph.svg dbpedia-ja:木幅 dbpedia-ja:グラフ彩色 dbpedia-ja:木分解 dbpedia-ja:グラフ理論 dbpedia-ja:パーフェクトグラフ dbpedia-ja:SIAM_Journal_on_Computing dbpedia-ja:区間グラフ dbpedia-ja:Distance-hereditary_graph dbpedia-ja:反マトロイド dbpedia-ja:スプリットグラフ dbpedia-ja:風車グラフ dbpedia-ja:ハミルトン閉路 dbpedia-ja:Journal_of_Combinatorial_Theory dbpedia-ja:アポロニアンネットワーク n12:Tree_decomposition.svg dbpedia-ja:プトレマイオスグラフ dbpedia-ja:クリーク_(グラフ理論) dbpedia-ja:SIAM_Journal_on_Discrete_Mathematics dbpedia-ja:ブロックグラフ dbpedia-ja:Theoretical_Computer_Science_(journal) dbpedia-ja:準閾値グラフ
dbo:wikiPageExternalLink
n5:gc_32.html n6:index.html n7:chordal.pdf n14:lexbfs.ps n16:1102995572 n21:14421
prop-ja:wikiPageUsesTemplate
template-ja:仮リンク template-ja:Harvnb template-ja:Harvtxt template-ja:Citation template-ja:Mathworld template-ja:Sfnp template-ja:Reflist
dbo:thumbnail
n10:Chordal-graph.svg?width=300
foaf:depiction
n10:Tree_decomposition.svg n10:Chordal-graph.svg
prop-ja:title
Chordal Graph
prop-ja:urlname
ChordalGraph
dbo:abstract
弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てが弦を持つようなグラフである。ここで、弦とは、閉路を構成しないが、閉路の2頂点をつなぐ辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である（4頂点以上の誘導グラフは閉路を持たないか、弦を持つ）。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、という頂点の順序付けが可能である」「最小頂点分離(minimal separator)（グラフを全域グラフでなくするために除去する必要最小限なグラフ）がクリークである」「木の部分木の」といった特徴も持つ。また、rigid circuit graphsや、triangulated graphとも呼ばれる。 弦グラフは完全グラフの部分グラフである。弦グラフを多項式時間で発見できることもあり、グラフ彩色のようなグラフ一般に対しては困難な問題も、弦グラフに対しては多項式時間で解ける場合もある。グラフの(treewidth)は、それを含む弦グラフのクリークのサイズによって特徴づけられるかも知れない。
foaf:isPrimaryTopicOf
wikipedia-ja:弦グラフ
dbo:wikiPageLength
12779
prov:wasDerivedFrom
wikipedia-ja:弦グラフ?oldid=79839481&ns=0
Subject Item
dbpedia-ja:木分解
dbo:wikiPageWikiLink
dbpedia-ja:弦グラフ
Subject Item
dbpedia-ja:グラフ_(離散数学)
dbo:wikiPageWikiLink
dbpedia-ja:弦グラフ
Subject Item
dbpedia-ja:グラフ彩色
dbo:wikiPageWikiLink
dbpedia-ja:弦グラフ
Subject Item
dbpedia-ja:ディラックの定理
dbo:wikiPageWikiLink
dbpedia-ja:弦グラフ
Subject Item
wikipedia-ja:弦グラフ
foaf:primaryTopic
dbpedia-ja:弦グラフ