## Graph theory |

**Graph theory** is a field of *vertex* (more than one are called *vertices*), and the lines are called *edges*. Graphs are a tool for modelling relationships. They are used to find answers to a number of problems.

Some of these questions are:

- What is the best way for a
mailman to get to all of thehouses in the area in the least amount oftime ? The points could representstreet corners and lines could represent the houses along the street. (seeChinese postman problem )

- A salesman has to visit different customers, but wants to keep the distance traveled as small as possible. The problem is to find a way so they can do it. This problem is known as
Travelling Salesman Problem (and often abbreviated*TSP*). It is among the hardest problems to solve. If a commonly believedconjecture is true (described as**P**≠**NP**), then an exact solution requires one to try all possible routes to find which is shortest.

- How many colors would be needed to color a map, if countries sharing a border are colored differently? The points could represent the different areas and the lines could represent that two areas are neighboring. (look at the
Four color theorem )

- Can a sketch be drawn in one closed line? The lines of the drawing are the lines of the graph and when two or more lines collide, there is a point in the graph. The task is now to find a way through the graph using each line one time. (look at
Seven Bridges of Königsberg )

- different kinds of graphs
- history
- graph theory in perspective
- references

- Graph theory has many aspects. Graphs can be directed or undirected. An example of a directed graph would be the system of roads in a city. Some streets in the city are one way streets. This means, that on those parts there is only one direction to follow.
- Graphs can be weighted. An example would be a road network, with distances, or with
tolls (for roads). - The nodes (the circles in the schematic) of a graph are called
vertices . The lines connecting the nodes are callededges . There can be no line between two nodes, there can be one line, or there can be multiple lines.

Other Languages

አማርኛ: ሥነ ግራፍ

العربية: نظرية المخططات

aragonés: Teoría de grafos

asturianu: Teoría de grafos

বাংলা: গ্রাফ তত্ত্ব

башҡортса: Графтар теорияһы

беларуская: Тэорыя графаў

български: Теория на графите

bosanski: Teorija grafikona

català: Teoria de grafs

Чӑвашла: Графсен теорийĕ

čeština: Teorie grafů

Cymraeg: Damcaniaeth graffiau

dansk: Grafteori

Deutsch: Graphentheorie

eesti: Graafiteooria

Ελληνικά: Θεωρία γράφων

English: Graph theory

español: Teoría de grafos

Esperanto: Grafeteorio

euskara: Grafo teoria

فارسی: نظریه گراف

français: Théorie des graphes

galego: Teoría de grafos

한국어: 그래프 이론

Հայերեն: Գրաֆների տեսություն

हिन्दी: ग्राफ़ सिद्धान्त

Bahasa Indonesia: Teori graf

íslenska: Netafræði

italiano: Teoria dei grafi

עברית: תורת הגרפים

қазақша: Графтар теориясы

latviešu: Grafu teorija

lietuvių: Grafų teorija

magyar: Gráfelmélet

македонски: Теорија на графови

Malti: Teorija tal-grafi

Bahasa Melayu: Teori graf

монгол: Графын онол

Nederlands: Grafentheorie

日本語: グラフ理論

norsk: Grafteori

norsk nynorsk: Grafteori

polski: Teoria grafów

português: Teoria dos grafos

română: Teoria grafurilor

русский: Теория графов

sicilianu: Tiuria dî grafi

slovenčina: Teória grafov

slovenščina: Teorija grafov

српски / srpski: Теорија графова

srpskohrvatski / српскохрватски: Teorija grafova

suomi: Verkkoteoria

svenska: Grafteori

Tagalog: Teoriya ng grap

ไทย: ทฤษฎีกราฟ

тоҷикӣ: Назарияи графҳо

Türkçe: Çizge teorisi

українська: Теорія графів

اردو: نظریۂ گراف

Tiếng Việt: Lý thuyết đồ thị

粵語: 圖論

中文: 图论