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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n19http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
dbpedia-kohttp://ko.dbpedia.org/resource/
n17https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-srhttp://sr.dbpedia.org/resource/
n10http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n4https://digitalcollections.anu.edu.au/bitstream/1885/49338/2/
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:FKT
dbo:wikiPageWikiLink
dbr:FKT_algorithm
dbo:wikiPageDisambiguates
dbr:FKT_algorithm
Subject Item
dbr:List_of_graph_theory_topics
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
dbr:Perfect_matching
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
dbr:Computing_the_permanent
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
dbr:Matching_(graph_theory)
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
dbr:Orientation_(graph_theory)
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
dbr:Harold_Neville_Vazeille_Temperley
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
dbr:Pfaffian
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
dbr:Holographic_algorithm
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
dbr:Pieter_Kasteleyn
dbo:wikiPageWikiLink
dbr:FKT_algorithm
dbp:knownFor
dbr:FKT_algorithm
dbo:knownFor
dbr:FKT_algorithm
Subject Item
dbr:Michael_Fisher
dbo:wikiPageWikiLink
dbr:FKT_algorithm
dbo:knownFor
dbr:FKT_algorithm
Subject Item
dbr:Tutte_polynomial
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
dbr:FKT_algorithm
rdf:type
yago:Algorithm105847438 yago:Activity100407535 yago:Event100029378 yago:VisualCommunication106873252 yago:Communication100033020 yago:Abstraction100002137 yago:Rule105846932 yago:Procedure101023820 yago:Graph107000195 yago:WikicatPlanarGraphs yago:YagoPermanentlyLocatedEntity yago:Act100030358 yago:WikicatGraphAlgorithms yago:PsychologicalFeature100023100
rdfs:label
Алгоритм FKT Algorithme FKT 파프 방향 FKT algorithm
rdfs:comment
L'algorithme FKT, nommé ainsi d'après Michael Fisher, (en) et Harold N. Temperley, compte le nombre de couplages parfaits dans un graphe planaire, et ceci en temps polynomial. Le même dénombrement est #P-complet pour les graphes généraux. Pour les couplages qui ne sont pas nécessairement parfaits, leur dénombrement reste #P-complet même pour les graphes planaires. L'idée clé de l'algorithme FKT est de convertir le problème en le calcul du pfaffien d'une matrice antisymétrique obtenue à partir d'un plongement planaire du graphe. Le pfaffien de cette matrice est ensuite calculé efficacement à l'aide d'algorithmes standards pour les déterminants . The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, counting them remains #P-complete even for planar graphs. The key idea of the FKT algorithm is to convert the problem into a Pfaffian computation of a skew-symmetric matrix derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standard determinant algorithms. 그래프 이론에서 파프 방향(Pfaff方向, 영어: Pfaffian orientation)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다. FKT (назван по именам Фишера, и ) — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя.
foaf:depiction
n10:Pfaffian_orientation_via_FKT_algorithm_example.gif
dcterms:subject
dbc:Graph_algorithms dbc:Planar_graphs
dbo:wikiPageID
30159370
dbo:wikiPageRevisionID
1051899726
dbo:wikiPageWikiLink
dbr:Complete_graph dbr:If_and_only_if dbr:Spanning_tree dbr:Regular_graph dbr:Tutte_matrix dbr:Partition_function_(statistical_mechanics) dbr:Lattice_graph dbr:Chemistry dbr:Diatomic_molecule dbr:Determinant dbr:Complete_bipartite_graph dbr:Matching_(graph_theory) dbr:Kuratowski's_theorem dbr:Sharp-P dbr:Pfaffian dbc:Graph_algorithms dbr:Hosoya_index dbr:Planar_graph dbr:P_(complexity) dbr:Perfect_matching dbr:Glossary_of_graph_theory dbr:Harold_Neville_Vazeille_Temperley dbr:Graph_embedding dbr:Pieter_Kasteleyn n19:Pfaffian_orientation_via_FKT_algorithm_example.gif dbr:Boolean_satisfiability_problem dbr:Pfaffian_orientation dbr:Dimer_(chemistry) dbr:Sharp-P-complete dbr:Homeomorphism_(graph_theory) dbr:Finite_graph dbr:Michael_Fisher dbr:Matchgates dbr:Dual_graph dbr:Vijay_Vazirani dbr:Statistical_mechanics dbr:Counting_problem_(complexity) dbr:Holographic_algorithm dbc:Planar_graphs dbr:Adjacency_matrix dbr:Arthur_Cayley dbr:Orientation_(graph_theory) dbr:Domino_tiling dbr:Skew-symmetric_matrix dbr:Parity_of_a_permutation dbr:FP_(complexity) dbr:H2O
dbo:wikiPageExternalLink
n4:02whole.pdf
owl:sameAs
yago-res:FKT_algorithm dbpedia-fa:الگوریتم_FKT n17:4jYdj dbpedia-sr:FKT_algoritam dbpedia-ru:Алгоритм_FKT freebase:m.0g5525_ dbpedia-fr:Algorithme_FKT dbpedia-ko:파프_방향 wikidata:Q5426031
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Reflist
dbo:thumbnail
n10:Pfaffian_orientation_via_FKT_algorithm_example.gif?width=300
dbo:abstract
그래프 이론에서 파프 방향(Pfaff方向, 영어: Pfaffian orientation)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다. L'algorithme FKT, nommé ainsi d'après Michael Fisher, (en) et Harold N. Temperley, compte le nombre de couplages parfaits dans un graphe planaire, et ceci en temps polynomial. Le même dénombrement est #P-complet pour les graphes généraux. Pour les couplages qui ne sont pas nécessairement parfaits, leur dénombrement reste #P-complet même pour les graphes planaires. L'idée clé de l'algorithme FKT est de convertir le problème en le calcul du pfaffien d'une matrice antisymétrique obtenue à partir d'un plongement planaire du graphe. Le pfaffien de cette matrice est ensuite calculé efficacement à l'aide d'algorithmes standards pour les déterminants . FKT (назван по именам Фишера, и ) — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя. The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, counting them remains #P-complete even for planar graphs. The key idea of the FKT algorithm is to convert the problem into a Pfaffian computation of a skew-symmetric matrix derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standard determinant algorithms.
prov:wasDerivedFrom
wikipedia-en:FKT_algorithm?oldid=1051899726&ns=0
dbo:wikiPageLength
12668
foaf:isPrimaryTopicOf
wikipedia-en:FKT_algorithm
Subject Item
dbr:Pfaffian_orientation
dbo:wikiPageWikiLink
dbr:FKT_algorithm
Subject Item
wikipedia-en:FKT_algorithm
foaf:primaryTopic
dbr:FKT_algorithm