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

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

Namespace Prefixes

Prefix	IRI
dbpedia-fr	http://fr.dbpedia.org/resource/
dbr	http://dbpedia.org/resource/
n19	http://mn.dbpedia.org/resource/
n62	http://www.orgnet.com/
dbpedia-no	http://no.dbpedia.org/resource/
dbpedia-uk	http://uk.dbpedia.org/resource/
n89	https://web.archive.org/web/20190517165158/http:/www.edutechlearners.com/download/
yago	http://dbpedia.org/class/yago/
foaf	http://xmlns.com/foaf/0.1/
dbpedia-et	http://et.dbpedia.org/resource/
dbpedia-el	http://el.dbpedia.org/resource/
n15	https://global.dbpedia.org/id/
dbpedia-ro	http://ro.dbpedia.org/resource/
dbp	http://dbpedia.org/property/
n87	http://ta.dbpedia.org/resource/
dbpedia-nn	http://nn.dbpedia.org/resource/
n94	http://ur.dbpedia.org/resource/
dbpedia-zh	http://zh.dbpedia.org/resource/
dbpedia-it	http://it.dbpedia.org/resource/
dbpedia-ca	http://ca.dbpedia.org/resource/
wikipedia-en	http://en.wikipedia.org/wiki/
dbpedia-pl	http://pl.dbpedia.org/resource/
dbpedia-id	http://id.dbpedia.org/resource/
n30	http://www.cs.rhul.ac.uk/books/dbook/
dbpedia-es	http://es.dbpedia.org/resource/
dbpedia-eo	http://eo.dbpedia.org/resource/
n34	https://books.google.com/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
dbpedia-az	http://az.dbpedia.org/resource/
dbpedia-ar	http://ar.dbpedia.org/resource/
dbpedia-hr	http://hr.dbpedia.org/resource/
dbpedia-an	http://an.dbpedia.org/resource/
n83	http://tl.dbpedia.org/resource/
dbpedia-th	http://th.dbpedia.org/resource/
n37	http://graphtheorysoftware.com/
dbpedia-is	http://is.dbpedia.org/resource/
rdfs	http://www.w3.org/2000/01/rdf-schema#
skos	http://www.w3.org/2004/02/skos/core#
prov	http://www.w3.org/ns/prov#
dbpedia-de	http://de.dbpedia.org/resource/
n103	http://scn.dbpedia.org/resource/
dbpedia-da	http://da.dbpedia.org/resource/
n67	http://lv.dbpedia.org/resource/
dbpedia-ka	http://ka.dbpedia.org/resource/
n72	http://ast.dbpedia.org/resource/
dbpedia-gl	http://gl.dbpedia.org/resource/
dbpedia-ms	http://ms.dbpedia.org/resource/
n82	http://hy.dbpedia.org/resource/
dbpedia-hu	http://hu.dbpedia.org/resource/
n12	http://tg.dbpedia.org/resource/
n22	http://hi.dbpedia.org/resource/
dbpedia-cs	http://cs.dbpedia.org/resource/
dbpedia-he	http://he.dbpedia.org/resource/
n24	https://web.archive.org/web/20161114100939/http:/www.babelgraph.org/
dcterms	http://purl.org/dc/terms/
n27	http://www.textgraphs.org/
yago-res	http://yago-knowledge.org/resource/
n69	https://www.edutechlearners.com/download/
n58	http://diestel-graph-theory.com/
dbpedia-tr	http://tr.dbpedia.org/resource/
n10	https://arxiv.org/abs/cond-mat/
dbpedia-be	http://be.dbpedia.org/resource/
n36	http://cv.dbpedia.org/resource/
n42	http://ba.dbpedia.org/resource/
dbo	http://dbpedia.org/ontology/
n41	http://d-nb.info/gnd/
owl	http://www.w3.org/2002/07/owl#
dbpedia-ko	http://ko.dbpedia.org/resource/
dbpedia-kk	http://kk.dbpedia.org/resource/
dbpedia-fi	http://fi.dbpedia.org/resource/
n31	http://lt.dbpedia.org/resource/
n33	http://www.gfredericks.com/main/sandbox/
dbpedia-fa	http://fa.dbpedia.org/resource/
dbpedia-sl	http://sl.dbpedia.org/resource/
dbpedia-sh	http://sh.dbpedia.org/resource/
dbt	http://dbpedia.org/resource/Template:
dbpedia-cy	http://cy.dbpedia.org/resource/
n100	http://zbw.eu/stw/descriptor/
n57	https://archive.org/details/
dbpedia-pt	http://pt.dbpedia.org/resource/
n74	http://ckb.dbpedia.org/resource/
dbpedia-ja	http://ja.dbpedia.org/resource/
n79	http://sw.cyc.com/concept/
wikidata	http://www.wikidata.org/entity/
gold	http://purl.org/linguistics/gold/
xsdh	http://www.w3.org/2001/XMLSchema#
n108	http://zbw.eu/stw/mapping/dbpedia/
dbpedia-simple	http://simple.dbpedia.org/resource/
dbpedia-sk	http://sk.dbpedia.org/resource/
n70	http://bs.dbpedia.org/resource/
n26	https://web.archive.org/web/20060206155001/http:/www.nd.edu/~networks/
dbpedia-bg	http://bg.dbpedia.org/resource/
n39	http://www.utm.edu/departments/math/graph/
n40	http://www.martinbroadhurst.com/
n20	http://www.kde.org/applications/education/rocs/
n28	http://dbpedia.org/resource/File:
n51	http://ky.dbpedia.org/resource/
n17	http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-ru	http://ru.dbpedia.org/resource/
dbpedia-sv	http://sv.dbpedia.org/resource/
dbpedia-mk	http://mk.dbpedia.org/resource/
dbpedia-commons	http://commons.dbpedia.org/resource/
n101	http://am.dbpedia.org/resource/
dbpedia-sr	http://sr.dbpedia.org/resource/
n18	https://my.siam.org/Store/Product/viewproduct/
dbpedia-nl	http://nl.dbpedia.org/resource/
n55	http://bn.dbpedia.org/resource/
freebase	http://rdf.freebase.com/ns/
dbpedia-vi	http://vi.dbpedia.org/resource/
dbpedia-eu	http://eu.dbpedia.org/resource/
dbc	http://dbpedia.org/resource/Category:

Statements

Subject Item

dbr:Graph_theory

rdf:type

owl:Thing yago:Location100027167 dbo:Book yago:Region108630985 yago:Field108569998 yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:YagoGeoEntity yago:Tract108673395 yago:PhysicalEntity100001930 yago:WikicatFieldsOfMathematics yago:Object100002684 yago:GeographicalArea108574314

rdfs:label

Grafentheorie Graphentheorie Teoria dei grafi Grafeteorio Teoria dos grafos Teori graf Teoría de grafos Теорія графів نظرية البيان Théorie des graphes Graph theory Grafo teoria Теория графов 그래프 이론 Θεωρία γράφων Teorie grafů Teoria grafów グラフ理論 图论 Grafteori Teoria de grafs

rdfs:comment

Grafeteorio estas branĉo de diskreta matematiko, kiu okupiĝas pri grafeoj. La ĉefnocio de la teorio, grafeo, difineblas kiel aro de verticoj (punktoj) kaj aro de eĝoj (linieroj), kiuj ligas kelkajn parojn de verticoj. Ekzemplo de grafeo estas reto de metroo, kie la aro de la stacioj respondas al la verticoj kaj la aro de la linieroj (inter po du stacioj) al la eĝoj de grafeo. La problemo pri la sep pontoj de Königsberg estas klasika problemo de grafeteorio; la solvo estas facila el grafeteoria vidpunkto. Teori graf dalam matematika dan ilmu komputer adalah cabang kajian yang mempelajari sifat-sifat "graf". Ini tidak sama dengan "Grafika". Graf merupakan sekumpulan objek terstruktur di mana beberapa pasangan objek mempunyai hubungan ataupun keterkaitan tertentu. Secara informal, suatu graf adalah himpunan benda-benda yang disebut "simpul" (vertex atau node) yang terhubung oleh "sisi" (edge) atau "busur" (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan "simpul") yang dihubungkan oleh garis-garis (melambangkan "sisi") atau garis berpanah (melambangkan "busur"). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan "gelang" (loop). In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Teorie grafů je obor diskrétní matematiky, který zkoumá vlastnosti takzvaných grafů. Graf je matematická struktura, definovaná množinou vrcholů a množinou hran, kde každá hrana je určena povinně dvěma vrcholy a volitelně směrem nebo váhou („cenou“); váha může odrážet např. délku, náklady na přesun nebo průchodnost. Graf si lze dobře představit jako mapu, na které vrcholy představují města a hrany představují dálnice, přičemž každá z těchto dálnic přímo spojuje dvě města. Grafy, jimiž se demonstruje smysl teorie grafů, se znázorňují zpravidla jako kroužky (reprezentace vrcholů) a úsečky (reprezentace hran) mezi těmito kroužky v rovině. Formálně je graf uspořádanou dvojicí množiny vrcholů a množiny hran : Teoria grafów – dział matematyki zajmujący się badaniem własności grafów. Za pierwszą pracę na temat teorii grafów uznawany jest opis zagadnienia mostów królewieckich, opublikowany w 1736 roku przez Leonharda Eulera. Algorytmy grafowe są także przedmiotem badań informatyki. Η θεωρία γράφων είναι ένα γνωστικό πεδίο των διακριτών μαθηματικών, με εφαρμογές στην πληροφορική, στις επιστήμες μηχανικών, στη χημεία, στην κοινωνιολογία κ.α. Αν και οι απαρχές της θεωρίας θεμελιώθηκαν κατά τον 18ο αιώνα, αναπτύχθηκε μεταπολεμικά ως ξεχωριστό πεδίο των εφαρμοσμένων μαθηματικών. Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E — підмножина V × V. Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез. 图论（英語：Graph theory），是组合数学分支，和其他数学分支如群论、矩阵论、拓扑学有着密切关系。 图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。 图论的研究对象相当于一维的单纯複形。 نظرية المخططات أو نظرية البيان (بالإنجليزية: Graph theory)‏ هي نظرية في الرياضيات وعلوم الحاسب، تدرس خواص المخططات حيث يتم تمثيل مجموعة كائنات تدعى رؤوسا، ترتبط ببعضها بأضلاع وتدعى أحيانا أقواسا، يمكن أن تكون موجهة أي مزودة باتجاه (تستخدم الاسهم بدل الأضلاع) أو بدون اتجاه (أضلاع فقط). التمثيل لهذا المخطط يكون على الورق بمجموعة نقاط تمثل الرؤوس متصلة بخطوط هي حروف (أضلاع أو أسهم) المخطط. رياضياً يُمكن أن يُعطى المخطط عبر مصفوفة المجاورة (Adjacency Matrix). Matematikan, grafo bat objektu multzo bat da, puntu edo erpin bitartez irudikatzen dena, objektu hauek lotzen dituzten lokarri edo ertzekin batera. Praktikan, grafoak errepide sareak, ekoizpen prozesu bateko uneak eta aldiak, pertsonen arteko harremanak eta abar irudikatu eta aztertzeko erabiltzen dira. Helburu praktiko horietarako, grafo teoriaren lagungarri den garatzen da. Zentzu hertsian, grafo teoria terminoa grafoa matematika puruaren aztergai gisa hartzen denean erabiltzen da. Normalean, grafo bat bikote ordenatu bat da non erpin ez hutsen multzoa da eta ertz multzoa da. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non-symétriques (les graphes sont alors dits orientés) et sont appelées des flèches ou des arcs. Тео́рия гра́фов — раздел дискретной математики, изучающий графы. В самом общем смысле граф — это множество точек (вершин, узлов), которые соединяются множеством линий (рёбер, дуг). Теория графов (то есть систем линий, соединяющих заданные точки) включена в учебные программы для начинающих математиков, поскольку: Теория графов, как математическое орудие, приложима как к наукам о поведении (теории информации, кибернетике, теории игр, теории систем, транспортным сетям), так и к чисто абстрактным дисциплинам (теории множеств, теории матриц, теории групп и так далее). и так далее. Die Graphentheorie (seltener auch Grafentheorie) ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Betrachtungsgegenstand der Graphentheorie sind Graphen (Mengen von Knoten und Kanten), deren Eigenschaften und ihre Beziehungen zueinander. 그래프 이론(문화어: 그라프리론, graph理論, 영어: graph theory；圖論，도론)은 수학에서 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프에 대한 연구이다. 이 문맥에서 그래프는 꼭짓점(버텍스/vertex), 교점(노드/node), 점(포인트/point)으로 구성되며 이것들은 변(엣지/edge, 간선), 즉 선으로 연결된다. 그래프는 무향(무방향성)일 수 있는데 이는 각 변(선)으로 연결되는 두 개의 꼭짓점 간에 구별이 없다는 의미이며, 한편 변은 한 꼭짓점에서 다른 꼭짓점 간에 방향이 있을 수도 있다. (더 자세한 정의와 이러한 유형의 그래프의 변종에 대해서는 그래프 이론 용어를 참고할 것) 그래프는 이산수학의 주요 논제 가운데 하나이다. 그래프 이론의 기초적인 정의에 대해서는 그래프 이론 용어를 참고할 것. La teoria de grafs és una branca de les matemàtiques i la informàtica que es dedica a l'estudi dels grafs, estructures matemàtiques utilitzades per a modelitzar relacions entre parelles d'objectes. En aquest context, un graf consisteix en una col·lecció de vèrtexs o nodes connectats per línies anomenades arestes. Els grafs poden ser no dirigits, és a dir sense fer distinció entre els dos vèrtexs associats a cada aresta, o dirigits, les arestes dels quals van d'un vèrtex a un altre; en aquest cas, les arestes s'anomenen arcs. Els grafs se solen representar gràficament amb un punt o cercle per cada vèrtex, i una línia entre vèrtexs connectats. Si el graf és dirigit, els arcs se simbolitzen amb fletxes, indicant la direcció de la relació entre els dos vèrtexs. グラフ理論（グラフりろん、英: Graph theory）は、ノード（節点・頂点、点）の集合とエッジ（枝・辺、線）の集合で構成されるグラフに関する数学の理論である。 グラフ（データ構造）などの応用がある。 La teoría de grafos, también llamada teoría de gráficas, es una rama de la matemática y las ciencias de la computación que estudia las propiedades de los grafos. Los grafos no deben ser confundidos con las gráficas, que es un término muy amplio. Formalmente, un grafo es una pareja ordenada en la que es un conjunto no vacío de vértices y es un conjunto de aristas. Donde consta de pares no ordenados de vértices, tales como , entonces se dice que e son adyacentes; y en el grafo se representa mediante una línea no orientada que una dichos vértices. Si el grafo es dirigido se le llama dígrafo, se denota , y entonces el par es un par ordenado, esto se representa con una flecha que va de a y se dice que .​ A teoria dos grafos ou de grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são utilizadas estruturas chamadas de grafos, , onde é um conjunto não vazio de objetos denominados vértices (ou nós) e (do inglês edges - arestas) é um subconjunto de pares não ordenados de V. De grafentheorie is een deelgebied van de wiskunde dat de eigenschappen van grafen bestudeert. Een graaf bestaat uit een verzameling punten, knopen genoemd, waarvan sommige verbonden zijn door lijnen, de zijden, kanten, takken of bogen. Afhankelijk van de toepassing kunnen de lijnen gericht zijn, dan worden ze ook wel pijlen genoemd, men spreekt dan van een gerichte graaf. Ook worden wel gewichten aan de lijnen toegekend door middel van getallen, deze stellen dan bijvoorbeeld de afstand tussen twee punten voor. Een graaf met gewichten noemt men een gewogen graaf. Grafteori är det område inom matematiken som undersöker egenskaper hos grafer. En graf är en mängd punkter, kallade noder eller hörn, sammanbundna med linjer, kallade bågar eller kanter. Anledningen till att man valt orden noder och bågar eller kanter och hörn istället för punkter och linjer är att kanter och hörn saknar de vanliga euklidiska egenskaperna för punkter och linjer. Man kan lägga flera punkter på samma linje, men en kant kan bara gå mellan max två hörn. Kanten kan dessutom gå tillbaka till samma hörn. Den kallas då loop. Antalet kantändar som ansluter till samma hörn kallas hörnets grad. Det är möjligt att flera kanter går mellan samma par av hörn. Det kallas multipla kanter. En väg i en graf är en sekvens av noder sådan att det från varje nod (förutom möjligen den sista) i se In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi è la disciplina che si occupa dello studio dei grafi, oggetti discreti che permettono di schematizzare una grande varietà di situazioni e processi, e spesso di consentirne delle analisi in termini quantitativi e algoritmici.

skos:exactMatch

n100:15038-0

foaf:depiction

n17:Konigsberg_bridges.png n17:Moreno_Sociogram_2nd_Grade.png n17:Directed.svg n17:Wikipedia_multilingual_network_graph_July_2013.svg n17:6n-graf.svg n17:Undirected.svg

dcterms:subject

dbc:Graph_theory

dbo:wikiPageID

12401

dbo:wikiPageRevisionID

1124812527

dbo:wikiPageWikiLink

dbr:Edge_coloring dbr:Percy_John_Heawood dbr:Optimality_theory dbr:Quantum_graph dbr:Distance_matrix dbr:Subdivision_(graph_theory) dbr:Perfect_graph dbr:Ralph_Faudree dbr:Network_science dbr:Lexical_semantics dbr:Electric_current dbr:Gustav_Kirchhoff dbr:Parsing dbr:Mathematical_structure dbr:George_Pólya_Prize dbr:Complete_graph dbr:Strongly_regular_graph dbr:Single-cell_analysis dbr:Arboricity dbr:Circle_packing_theorem dbr:John_Adrian_Bondy dbr:Borůvka's_algorithm dbr:Endre_Szemerédi dbr:Computer_science dbr:Subgraph_isomorphism_problem dbr:Max_flow_min_cut_theorem dbr:Gallery_of_named_graphs dbr:Hypergraph dbr:Traveling_salesman_problem dbr:Museum_guard_problem dbr:William_Rowan_Hamilton dbr:Binary_relation dbr:Gottfried_Wilhelm_Leibniz dbr:Vertex_(graph_theory) dbr:Knight's_Tour dbr:Homeomorphism_(graph_theory) dbr:Robin_Thomas_(mathematician) dbr:Quiver_(mathematics) dbr:Graph_algebra dbr:Condensed_matter_physics dbr:Network_simplex_algorithm dbr:Biological_pathway dbr:Dual-phase_evolution dbr:August_Kekulé dbr:Induced_subgraph dbr:Frank_Harary dbr:Null_graph dbr:Vertex_cover_problem dbr:Graph_isomorphism_problem dbr:Semantic_networks dbr:Julius_Petersen dbr:Syntax dbr:Covering_problem dbr:Conceptual_graph dbr:Semantic_network dbr:Network_theory dbr:Transitive_reduction dbr:Wagner's_theorem dbr:Graph_automorphism n28:Undirected.svg dbr:Graph_drawing dbr:Percolation_theory dbr:Graph_enumeration dbr:Graph_equation dbr:Four-color_theorem dbr:James_Joseph_Sylvester dbr:Graph_factorization dbr:Planarity_(graph_theory) dbr:Pál_Turán n28:Konigsberg_bridges.png dbr:Kirchhoff's_circuit_laws dbr:Mehdi_Behzad dbr:Jaroslav_Nešetřil dbr:Graph_property dbr:Set_(mathematics) dbr:Differential_calculus dbr:Ramsey_theory dbr:Extremal_graph_theory dbr:Graph_rewriting dbr:Group_theory dbr:Graph_sandwich_problem dbr:Persistence_(computer_science) dbr:Topological_graph_theory dbr:W._T._Tutte dbr:Push–relabel_maximum_flow_algorithm dbr:Gabriel_Andrew_Dirac dbr:Kruskal's_algorithm dbr:Independent_set_problem dbr:Graphical_enumeration dbr:Paul_Erdős dbr:Loop_(graph_theory) dbr:Website dbr:Hadwiger_conjecture_(graph_theory) dbr:Multiple_edges dbr:List_of_publications_in_mathematics dbr:Directed_acyclic_graph dbr:Route_inspection_problem dbr:Electric_circuit dbr:Four_color_problem dbr:Claude_Berge dbr:List_of_unsolved_problems_in_graph_theory dbr:Kirchhoff's_theorem dbr:László_Lovász dbr:Independent_set_(graph_theory) dbr:Representation_(mathematics) dbr:Sparse_graph dbr:Cybernetics dbr:Herbert_Fleischner dbr:Computational_linguistics dbr:Edsger_W._Dijkstra dbr:Paul_Seymour_(mathematician) dbr:Laplacian_matrix dbr:Academic_Press dbr:Forbidden_graph_characterization dbr:Bellman–Ford_algorithm dbr:Data_structure dbr:K-vertex-connected_graph dbr:Béla_Bollobás dbr:Alexandre-Théophile_Vandermonde dbr:Social_network_analysis dbr:Geometric_graph_theory dbr:Physics dbr:George_Pólya dbr:Graham_Brightwell dbr:Random_regular_graph dbr:Peter_Tait_(physicist) dbr:Existential_graph dbr:Computational_neuroscience dbr:Seven_Bridges_of_Königsberg dbr:Set_cover_problem dbr:Connectomics dbr:Chemistry dbr:NP-complete_problem dbr:Depth-first_search dbr:Kosaraju's_algorithm dbc:Graph_theory dbr:Shortest_path dbr:Shortest_path_problem dbr:List_edge-coloring dbr:U._S._R._Murty dbr:Head-driven_phrase_structure_grammar dbr:Cycle_double_cover dbr:Anton_Kotzig dbr:Hamiltonian_path_problem dbr:Ford–Fulkerson_algorithm dbr:Neil_Robertson_(mathematician) dbr:Quantum_field_theory dbr:Reconstruction_conjecture dbr:Dijkstra's_algorithm dbr:Incidence_matrix dbr:List_of_graph_theory_topics dbr:Alfred_Kempe dbr:Seven_bridges_of_Königsberg n28:Directed.svg dbr:Discrete_mathematics dbr:Nicolaas_Govert_de_Bruijn dbr:Dominating_set dbr:Kenneth_Appel dbr:Database_transaction dbr:Matrix(mathematics) dbr:Cambridge_University_Press dbr:Leonhard_Euler dbr:Pseudograph dbr:Unordered_pair dbr:Johann_Benedict_Listing dbr:Prim's_algorithm dbr:Spectral_graph_theory dbr:Maria_Chudnovsky dbr:Topological_sorting dbr:Tarjan's_strongly_connected_components_algorithm dbr:Degree_(graph_theory) dbr:Voltage dbr:Simon_Antoine_Jean_L'Huilier dbr:Nearest_neighbour_algorithm dbr:Automatic_theorem_prover dbr:Knight's_tour dbr:Strong_perfect_graph_theorem dbr:Gerhard_Ringel dbr:Random_graph dbr:Hungarian_algorithm dbr:Principle_of_compositionality dbr:Degree_matrix dbr:Matching_(graph_theory) dbr:Porous_medium dbr:Kazimierz_Kuratowski dbr:Combinatorics dbr:Carsten_Thomassen dbr:Topology dbr:North-Holland_Publishing_Company dbr:Pebble_motion_problems dbr:Floyd–Warshall_algorithm dbr:Steiner_tree dbr:Intersection_graph dbr:Hyperlink dbr:Kelmans–Seymour_conjecture dbr:Molecular_graph dbr:Finite-state_transducer dbr:Ordered_pair dbr:Chemical_bond dbr:Breadth-first_search dbr:Molecule_editor dbr:Neighbourhood_(graph_theory) dbr:Graph_properties dbr:Camille_Jordan dbr:Disjoint-set_data_structure dbr:Chemical_graph_theory dbr:Weighted_graph dbr:Feynman_diagram dbr:Daniel_P._Sanders dbr:Genus_(mathematics) dbr:Flow_network dbr:Sociology dbr:Principle_of_Compositionality dbr:Augustin-Louis_Cauchy dbr:Linguistics dbr:Algebraic_graph_theory dbr:Knot_theory dbr:Regular_graph dbr:Partial_order n28:6n-graf.svg n28:Wikipedia_multilingual_network_graph_July_2013.svg dbr:Königsberg dbr:Fan_Chung dbr:Arthur_Cayley dbr:Edmonds–Karp_algorithm dbr:Clique_problem dbr:Graph_(data_structure) dbr:Graph_(discrete_mathematics) dbr:Heinrich_Heesch dbr:Dénes_Kőnig dbr:Spanning_tree dbr:Hugo_Hadwiger dbr:Graph_transformation dbr:Atom dbr:Ronald_Graham dbr:Genomics dbr:Feature_structure dbr:Tree_(data_structure) dbr:Planarity_testing dbr:Tree_(graph_theory) dbr:Statistical_physics dbr:Martin_Charles_Golumbic dbr:Citation_graph dbr:Graph_coloring dbr:Algorithm dbr:Graph_database dbr:Total_coloring dbr:Glossary_of_graph_theory dbr:Glossary_of_graph_theory_terms dbr:Nature_(journal) dbr:Decision_problem dbr:Infinite_graph dbr:Multigraph dbr:Edge_list dbr:Francis_Guthrie dbr:Three-cottage_problem n28:Moreno_Sociogram_2nd_Grade.png dbr:Molecular_biology dbr:Enumeration_of_graphs dbr:Hassler_Whitney dbr:Erdős–Faber–Lovász_conjecture dbr:WordNet dbr:Biology dbr:Hopcroft–Karp_algorithm dbr:Kuratowski's_theorem dbr:VerbNet dbr:Frank_P._Ramsey dbr:Lattice_graph dbr:Entitative_graph dbr:Adjacency_list dbr:Adjacency_matrix dbr:Alfréd_Rényi dbr:Crossing_number_(graph_theory) dbr:Augustus_De_Morgan dbr:Minor_(graph_theory) dbr:Rumor_spread_in_social_network dbr:Noga_Alon dbr:Abstract_simplicial_complex dbr:Planar_graph dbr:Logical_graph dbr:Wolfgang_Haken dbr:Six_Degrees_of_Kevin_Bacon dbr:Complete_bipartite_graph dbr:Benny_Sudakov dbr:Symmetric_graph dbr:Minimum_spanning_tree dbr:Mathematics

dbo:wikiPageExternalLink

n10:0602129 n18:%3FProductId=106663 n20: n24:links.html n27: n30: n33:graphs n34:books%3Fid=vaXv_yhefG8C n37: n39: n40:Graph-algorithms.html n57:introductorygrap0000char%7Curl-access=registration n58:index.html n62:SocialLifeOfRouters.pdf n69:Graphtheory.pdf n26:gallery.htm n89:Graphtheory.pdf

owl:sameAs

dbpedia-he:תורת_הגרפים dbpedia-da:Grafteori dbpedia-vi:Lý_thuyết_đồ_thị n12:Назарияи_графҳо dbpedia-nl:Grafentheorie dbpedia-commons:Graph_theory n15:L3a9 n19:Графын_онол dbpedia-nn:Grafteori n22:ग्राफ़_सिद्धान्त wikidata:Q131476 freebase:m.0382k n31:Grafų_teorija dbpedia-gl:Teoría_de_grafos dbpedia-bg:Теория_на_графите n36:Графсен_теорийĕ dbpedia-th:ทฤษฎีกราฟ n41:4113782-6 n42:Графтар_теорияһы dbpedia-kk:Графтар_теориясы dbpedia-zh:图论 dbpedia-sk:Teória_grafov dbpedia-tr:Çizge_teorisi dbpedia-el:Θεωρία_γράφων dbpedia-sr:Теорија_графова dbpedia-eu:Grafo_teoria n51:Графтар_теориясы dbpedia-fi:Verkkoteoria dbpedia-de:Graphentheorie dbpedia-fa:نظریه_گراف n55:গ্রাফ_তত্ত্ব dbpedia-cy:Damcaniaeth_graffiau dbpedia-sv:Grafteori dbpedia-it:Teoria_dei_grafi dbpedia-ms:Teori_graf yago-res:Graph_theory n67:Grafu_teorija dbpedia-ro:Teoria_grafurilor n70:Teorija_grafova dbpedia-sh:Teorija_grafova n72:Teoría_de_grafos dbpedia-cs:Teorie_grafů n74:تیۆریی_گراف dbpedia-fr:Théorie_des_graphes dbpedia-ar:نظرية_البيان dbpedia-uk:Теорія_графів dbpedia-es:Teoría_de_grafos n79:Mx4rvt3YbJwpEbGdrcN5Y29ycA dbpedia-be:Тэорыя_графаў dbpedia-id:Teori_graf n82:Գրաֆների_տեսություն n83:Teorya_ng_grap dbpedia-hr:Teorija_grafova dbpedia-et:Graafiteooria n87:கோட்டுருவியல் dbpedia-sl:Teorija_grafov dbpedia-mk:Теорија_на_графови dbpedia-pl:Teoria_grafów dbpedia-ru:Теория_графов dbpedia-hu:Gráfelmélet n94:نظریۂ_گراف dbpedia-pt:Teoria_dos_grafos dbpedia-no:Grafteori dbpedia-eo:Grafeteorio dbpedia-az:Qraf_nəzəriyyəsi n101:ሥነ_ግራፍ dbpedia-an:Teoría_de_grafos n103:Tiuria_dî_grafi dbpedia-ja:グラフ理論 dbpedia-ko:그래프_이론 dbpedia-is:Netafræði dbpedia-ka:გრაფთა_თეორია dbpedia-ca:Teoria_de_grafs dbpedia-simple:Graph_theory

dbp:wikiPageUsesTemplate

dbt:Commons dbt:Short_description dbt:About dbt:Library_resources_about dbt:Further dbt:Reflist dbt:Computer_science dbt:Div_col dbt:Div_col_end dbt:Authority_control dbt:Cite_book dbt:Main dbt:Webarchive dbt:Areas_of_mathematics dbt:Nobreak dbt:Graph_Analysis_Software dbt:Springer dbt:Sfrac dbt:Sfn

dbo:thumbnail

n17:6n-graf.svg?width=300

dbp:colwidth

20

dbp:date

2006-02-06

dbp:id

p/g045010

dbp:label

graph theory

dbp:small

yes

dbp:title

Image gallery: graphs Graph theory

dbp:url

n26:gallery.htm

dbo:abstract

图论（英語：Graph theory），是组合数学分支，和其他数学分支如群论、矩阵论、拓扑学有着密切关系。 图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。 图论的研究对象相当于一维的单纯複形。 Η θεωρία γράφων είναι ένα γνωστικό πεδίο των διακριτών μαθηματικών, με εφαρμογές στην πληροφορική, στις επιστήμες μηχανικών, στη χημεία, στην κοινωνιολογία κ.α. Αν και οι απαρχές της θεωρίας θεμελιώθηκαν κατά τον 18ο αιώνα, αναπτύχθηκε μεταπολεμικά ως ξεχωριστό πεδίο των εφαρμοσμένων μαθηματικών. Στην ελληνική ορολογία οι όροι θεωρία γραφημάτων και θεωρία γράφων χρησιμοποιούνται ως ισοδύναμοι. Προτιμάται ο όρος γράφος, για να διακρίνεται από το γράφημα συνάρτησης. Ανάμεσα στους ποικίλους ορισμούς που απαντώνται, ένας σχετικά πλήρης ορίζει πως η θεωρία γράφων είναι η μελέτη των γράφων (γραφημάτων) και των σχέσεών τους. Οι μαθηματικοί υπολογισμοί επί των γράφων υλοποιούνται με συγκεκριμένους αλγόριθμους. Με γράφους μπορούν να μοντελοποιηθούν πολλές διαφορετικές φυσικές ή τεχνολογικές δομές, όπως π.χ. τα δίκτυα υπολογιστών, όπου το διάγραμμα ενός δικτύου ως ένας απλός κατευθυνόμενος γράφος. Grafteori är det område inom matematiken som undersöker egenskaper hos grafer. En graf är en mängd punkter, kallade noder eller hörn, sammanbundna med linjer, kallade bågar eller kanter. Anledningen till att man valt orden noder och bågar eller kanter och hörn istället för punkter och linjer är att kanter och hörn saknar de vanliga euklidiska egenskaperna för punkter och linjer. Man kan lägga flera punkter på samma linje, men en kant kan bara gå mellan max två hörn. Kanten kan dessutom gå tillbaka till samma hörn. Den kallas då loop. Antalet kantändar som ansluter till samma hörn kallas hörnets grad. Det är möjligt att flera kanter går mellan samma par av hörn. Det kallas multipla kanter. En väg i en graf är en sekvens av noder sådan att det från varje nod (förutom möjligen den sista) i sekvensen finns en båge till nästa nod i sekvensen. De grafentheorie is een deelgebied van de wiskunde dat de eigenschappen van grafen bestudeert. Een graaf bestaat uit een verzameling punten, knopen genoemd, waarvan sommige verbonden zijn door lijnen, de zijden, kanten, takken of bogen. Afhankelijk van de toepassing kunnen de lijnen gericht zijn, dan worden ze ook wel pijlen genoemd, men spreekt dan van een gerichte graaf. Ook worden wel gewichten aan de lijnen toegekend door middel van getallen, deze stellen dan bijvoorbeeld de afstand tussen twee punten voor. Een graaf met gewichten noemt men een gewogen graaf. Structuren die als grafen weergegeven kunnen worden, komen veel voor. Grafen worden bijvoorbeeld gebruikt om eindigetoestandsautomaten te modelleren, om een schematische routekaart te maken tussen een aantal plaatsen met de afstanden daartussen en bij patroonvergelijking. Verschillende soorten grafen spelen in de informatica nog een rol, niet alleen in de vorm van boomstructuren, maar ook om gegevensoverdracht over netwerken weer te geven. Er kunnen algoritmes worden uitgevoerd om bepaalde eigenschappen van zo'n graaf te berekenen en aan de hand daarvan voorspellingen te doen of beslissingen te nemen over de optimale route voor een datapakket. Dit is binnen de informatica dan ook een belangrijk onderwerp. Complexe netwerken vormen een vrij recent gebied in het onderzoek rond grafen, dat minder is gericht op de studie van kleine grafen en de eigenschappen van individuele knopen en zijden in deze grafen, maar eerder op de statistische eigenschappen van grootschalige netwerken. 그래프 이론(문화어: 그라프리론, graph理論, 영어: graph theory；圖論，도론)은 수학에서 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프에 대한 연구이다. 이 문맥에서 그래프는 꼭짓점(버텍스/vertex), 교점(노드/node), 점(포인트/point)으로 구성되며 이것들은 변(엣지/edge, 간선), 즉 선으로 연결된다. 그래프는 무향(무방향성)일 수 있는데 이는 각 변(선)으로 연결되는 두 개의 꼭짓점 간에 구별이 없다는 의미이며, 한편 변은 한 꼭짓점에서 다른 꼭짓점 간에 방향이 있을 수도 있다. (더 자세한 정의와 이러한 유형의 그래프의 변종에 대해서는 그래프 이론 용어를 참고할 것) 그래프는 이산수학의 주요 논제 가운데 하나이다. 그래프 이론의 기초적인 정의에 대해서는 그래프 이론 용어를 참고할 것. نظرية المخططات أو نظرية البيان (بالإنجليزية: Graph theory)‏ هي نظرية في الرياضيات وعلوم الحاسب، تدرس خواص المخططات حيث يتم تمثيل مجموعة كائنات تدعى رؤوسا، ترتبط ببعضها بأضلاع وتدعى أحيانا أقواسا، يمكن أن تكون موجهة أي مزودة باتجاه (تستخدم الاسهم بدل الأضلاع) أو بدون اتجاه (أضلاع فقط). التمثيل لهذا المخطط يكون على الورق بمجموعة نقاط تمثل الرؤوس متصلة بخطوط هي حروف (أضلاع أو أسهم) المخطط. رياضياً يُمكن أن يُعطى المخطط عبر مصفوفة المجاورة (Adjacency Matrix). تُمكن الاستعانة بالمخططات من حلحلة الكثير من المشاكل العملية، فمثلا بنية موسوعة ويكيبيديا يمكن تمثيلها بمخطط رؤوسه هي أسماء المقالات ونقوم برسم خط موجه بين مقالتين من أ إلى ب إذا كانت المقالة أ تحوي رابطا إلى المقالة ب. تطبيقات هذه النظرية واسعة جدا ولحل مشاكلها يستخدم الحاسوب بشكل واسع. لذلك تهتم علوم الحاسوب بتصميم خوارزميات لنظرية المخططات حيث يمكن معالجة أي مخطط لتمييز خصائصه واستخلاص المعلومات منه. グラフ理論（グラフりろん、英: Graph theory）は、ノード（節点・頂点、点）の集合とエッジ（枝・辺、線）の集合で構成されるグラフに関する数学の理論である。 グラフ（データ構造）などの応用がある。 A teoria dos grafos ou de grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são utilizadas estruturas chamadas de grafos, , onde é um conjunto não vazio de objetos denominados vértices (ou nós) e (do inglês edges - arestas) é um subconjunto de pares não ordenados de V. Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm um sentido associado (indicado por uma seta na representação gráfica) temos um dígrafo (grafo orientado). Um grafo com um único vértice e sem arestas é conhecido como grafo trivial. Estruturas que podem ser representadas por grafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de ligações da Wikipédia pode ser representada por um dígrafo: os vértices são os artigos da Wikipédia e existe uma aresta do artigo A para o artigo B se e somente se A contém um link para B. Dígrafos são também usados para representar máquinas de estado finito. O desenvolvimento de algoritmos para manipular grafos é um tema importante da ciência da computação. Grafeteorio estas branĉo de diskreta matematiko, kiu okupiĝas pri grafeoj. La ĉefnocio de la teorio, grafeo, difineblas kiel aro de verticoj (punktoj) kaj aro de eĝoj (linieroj), kiuj ligas kelkajn parojn de verticoj. Ekzemplo de grafeo estas reto de metroo, kie la aro de la stacioj respondas al la verticoj kaj la aro de la linieroj (inter po du stacioj) al la eĝoj de grafeo. La problemo pri la sep pontoj de Königsberg estas klasika problemo de grafeteorio; la solvo estas facila el grafeteoria vidpunkto. Sinonimoj de grafeteorio estas grafeiko kaj teorio de grafeoj. Anstataŭ la termino "grafeo", en literaturo oni povas vidi ankaŭ la terminojn grafo kaj grafio. Teorie grafů je obor diskrétní matematiky, který zkoumá vlastnosti takzvaných grafů. Graf je matematická struktura, definovaná množinou vrcholů a množinou hran, kde každá hrana je určena povinně dvěma vrcholy a volitelně směrem nebo váhou („cenou“); váha může odrážet např. délku, náklady na přesun nebo průchodnost. Graf si lze dobře představit jako mapu, na které vrcholy představují města a hrany představují dálnice, přičemž každá z těchto dálnic přímo spojuje dvě města. Grafy, jimiž se demonstruje smysl teorie grafů, se znázorňují zpravidla jako kroužky (reprezentace vrcholů) a úsečky (reprezentace hran) mezi těmito kroužky v rovině. Formálně je graf uspořádanou dvojicí množiny vrcholů a množiny hran : . Původ teorie grafů sahá až do 18. století, kdy její zakladatel Leonhard Euler řešil úlohu sedm mostů města Královce. Jedním z hlavních cílů teorie grafů je poskytnout aparát, jímž je možné vyjadřovat vzájemné „vzdálenosti“ (vzdálenosti v širším slova smyslu) jednotlivých dvojic vrcholů. Výsledkem je model reálné sítě. Na problém teorie grafů lze formalizovat problémy z nejrůznějších vědních oborů i praktického života. Příkladem z první kategorie je analýza dopravy nebo provozu v počítačových sítích, z druhéhou soudku lze uvést kupř. strukturu vzájemného propojení článků Wikipedie – jednotlivé články jsou vrcholy grafu a odkaz z článku A na článek B je orientovanou hranou mezi vrcholy A a B. In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi è la disciplina che si occupa dello studio dei grafi, oggetti discreti che permettono di schematizzare una grande varietà di situazioni e processi, e spesso di consentirne delle analisi in termini quantitativi e algoritmici. La teoría de grafos, también llamada teoría de gráficas, es una rama de la matemática y las ciencias de la computación que estudia las propiedades de los grafos. Los grafos no deben ser confundidos con las gráficas, que es un término muy amplio. Formalmente, un grafo es una pareja ordenada en la que es un conjunto no vacío de vértices y es un conjunto de aristas. Donde consta de pares no ordenados de vértices, tales como , entonces se dice que e son adyacentes; y en el grafo se representa mediante una línea no orientada que una dichos vértices. Si el grafo es dirigido se le llama dígrafo, se denota , y entonces el par es un par ordenado, esto se representa con una flecha que va de a y se dice que .​ La teoría de grafos tiene sus fundamentos en la matemática discreta y de la matemática aplicada. Esta teoría requiere de diferentes conceptos de diversas áreas como combinatoria, álgebra, probabilidad, geometría de polígonos, aritmética y topología. Actualmente ha tenido mayor influencia en el campo de la informática, las ciencias de la computación y telecomunicaciones. Debido a la gran cantidad de aplicaciones en la optimización de recorridos, procesos, flujos, algoritmos de búsquedas, entre otros, se generó toda una nueva teoría que se conoce como análisis de redes.​ Die Graphentheorie (seltener auch Grafentheorie) ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Betrachtungsgegenstand der Graphentheorie sind Graphen (Mengen von Knoten und Kanten), deren Eigenschaften und ihre Beziehungen zueinander. Graphen sind mathematische Modelle für netzartige Strukturen in Natur und Technik (wie soziale Strukturen, Straßennetze, Computernetze, elektrische Schaltungen, Versorgungsnetze oder chemische Moleküle). In der Graphentheorie untersucht man lediglich die abstrakte Netzstruktur an sich. Die Art, Lage und Beschaffenheit der Knoten und Kanten bleibt unberücksichtigt. Es verbleiben jedoch viele allgemeingültige Graphen-Eigenschaften, die bereits auf dieser Abstraktionsstufe untersucht werden können und sich in allgemeingültigen Aussagen (Sätze der Graphentheorie) wiederfinden. Ein Beispiel hierfür ist das Handschlaglemma, wonach die Summe der Knotengrade in einem Graphen stets gerade ist (in der nebenstehenden Abbildung: vierzehn). Dadurch, dass einerseits viele algorithmische Probleme auf Graphen zurückgeführt werden können und andererseits die Lösung graphentheoretischer Probleme oft auf Algorithmen basiert, ist die Graphentheorie auch in der Informatik, insbesondere der Komplexitätstheorie, von großer Bedeutung. Die Untersuchung von Graphen ist auch Inhalt der Netzwerktheorie. Graphen werden insbesondere durch die Datenstrukturen Adjazenzmatrix, Inzidenzmatrix oder Adjazenzliste repräsentiert. Teori graf dalam matematika dan ilmu komputer adalah cabang kajian yang mempelajari sifat-sifat "graf". Ini tidak sama dengan "Grafika". Graf merupakan sekumpulan objek terstruktur di mana beberapa pasangan objek mempunyai hubungan ataupun keterkaitan tertentu. Secara informal, suatu graf adalah himpunan benda-benda yang disebut "simpul" (vertex atau node) yang terhubung oleh "sisi" (edge) atau "busur" (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan "simpul") yang dihubungkan oleh garis-garis (melambangkan "sisi") atau garis berpanah (melambangkan "busur"). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan "gelang" (loop). Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada Facebook bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para pengguna Facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman. Perkembangan algoritme untuk menangani graf akan berdampak besar bagi ilmu komputer. Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut atau digraf (directed graph). Digraf dengan sisi berbobot disebut . Jaringan banyak digunakan pada cabang praktis teori graf yaitu . Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah). Тео́рия гра́фов — раздел дискретной математики, изучающий графы. В самом общем смысле граф — это множество точек (вершин, узлов), которые соединяются множеством линий (рёбер, дуг). Теория графов (то есть систем линий, соединяющих заданные точки) включена в учебные программы для начинающих математиков, поскольку: * как и геометрия, обладает наглядностью; * как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи; * не имеет громоздкого математического аппарата («комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений»); * имеет выраженный прикладной характер. На протяжении более сотни лет развитие теории графов определялось в основном проблемой четырёх красок. Решение этой задачи в 1976 году оказалось поворотным моментом истории теории графов, после которого произошло её развитие как основы современной прикладной математики. Универсальность графов незаменима при проектировании и анализе коммуникационных сетей. Теория графов, как математическое орудие, приложима как к наукам о поведении (теории информации, кибернетике, теории игр, теории систем, транспортным сетям), так и к чисто абстрактным дисциплинам (теории множеств, теории матриц, теории групп и так далее). Несмотря на разнообразные, усложнённые, малопонятные и специализированные термины многие модельные (схемные, структурные) и конфигурационные проблемы переформулируются на языке теории графов, что позволяет значительно проще выявить их концептуальные трудности. В разных областях знаний понятие «граф» может встречаться под следующими названиями: * структура (гражданское строительство); * сеть (электротехника); * социограмма (социология и экономика); * молекулярная структура (химия); * навигационная карта (картография); * распределительная сеть (энергетика) и так далее. La teoria de grafs és una branca de les matemàtiques i la informàtica que es dedica a l'estudi dels grafs, estructures matemàtiques utilitzades per a modelitzar relacions entre parelles d'objectes. En aquest context, un graf consisteix en una col·lecció de vèrtexs o nodes connectats per línies anomenades arestes. Els grafs poden ser no dirigits, és a dir sense fer distinció entre els dos vèrtexs associats a cada aresta, o dirigits, les arestes dels quals van d'un vèrtex a un altre; en aquest cas, les arestes s'anomenen arcs. Els grafs se solen representar gràficament amb un punt o cercle per cada vèrtex, i una línia entre vèrtexs connectats. Si el graf és dirigit, els arcs se simbolitzen amb fletxes, indicant la direcció de la relació entre els dos vèrtexs. Els grafs són un dels principals objectes d'estudi de la matemàtica discreta. Les aplicacions de la teoria de grafs giren al voltant d'estructures que poden ser sistematitzades amb grafs, com per exemple l'estructura de llocs web, l'anàlisi de xarxes, l'estudi de molècules en química i física, o altres camps com els estudis sociològics. El primer problema conegut de la teoria de grafs és el problema dels set ponts de Königsberg. Fou plantejat per Leonhard Euler el 1736 . Matematikan, grafo bat objektu multzo bat da, puntu edo erpin bitartez irudikatzen dena, objektu hauek lotzen dituzten lokarri edo ertzekin batera. Praktikan, grafoak errepide sareak, ekoizpen prozesu bateko uneak eta aldiak, pertsonen arteko harremanak eta abar irudikatu eta aztertzeko erabiltzen dira. Helburu praktiko horietarako, grafo teoriaren lagungarri den garatzen da. Zentzu hertsian, grafo teoria terminoa grafoa matematika puruaren aztergai gisa hartzen denean erabiltzen da. Normalean, grafo bat bikote ordenatu bat da non erpin ez hutsen multzoa da eta ertz multzoa da. Grafo teoria bere oinarriak matematika diskretuan eta matematika aplikatuan ditu. Teoria bat da non zenbait arlotako kontzeptu behar dira konbinatoria, aljebra, probabilitatea, poligonoen geometria, aritmetika eta tipologia. Gaur egun gero eta nagusitasun handiago izan du informatikaren arloan, eta telekomunikazioetan. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non-symétriques (les graphes sont alors dits orientés) et sont appelées des flèches ou des arcs. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau (réseau social, réseau informatique, télécommunications, etc.) et dans bien d'autres domaines (par exemple génétique) tant le concept de graphe, à peu près équivalent à celui de relation binaire (à ne pas confondre donc avec graphe d'une fonction), est général. De grands théorèmes difficiles, comme le théorème des quatre couleurs, le théorème des graphes parfaits, ou encore le théorème de Robertson-Seymour, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la conjecture de Hadwiger, en font une branche vivace des mathématiques discrètes. Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E — підмножина V × V. Визначення графа є настільки загальним, що цим терміном можна описувати безліч подій та об'єктів повсякденного життя. Високий рівень абстракції та узагальнення дозволяє використовувати типові алгоритми теорії графів для вирішення зовнішньо несхожих задач у і комп'ютерних мережах, будівельному проектуванні, молекулярному моделюванні тощо. Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або запроектовані будинки, споруди, квартали тощо розглядаються як вершини, а дороги, інженерні мережі, лінії електропередачі, що їй з'єднують, тощо — як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут. Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез. Teoria grafów – dział matematyki zajmujący się badaniem własności grafów. Za pierwszą pracę na temat teorii grafów uznawany jest opis zagadnienia mostów królewieckich, opublikowany w 1736 roku przez Leonharda Eulera. Algorytmy grafowe są także przedmiotem badań informatyki.

dbp:lcheading

Graph theory

dbp:onlinebooks

yes

gold:hypernym

dbr:Study

prov:wasDerivedFrom

wikipedia-en:Graph_theory?oldid=1124812527&ns=0

dbo:wikiPageLength

51914

dcterms:isPartOf

n108:target

foaf:isPrimaryTopicOf

wikipedia-en:Graph_theory