^^Grafo.

Esempi wp/List_of_graphs

graph (undirected)

G = (V, E)   graph G is an ordered pair of sets (V, E)

• V set of  points
• E set of lines, made of unordered pairs {., .} of points

vo:

1. points ≡ nodes ≡ vertices V
   lines ≡ links ≡ edges E
2. vertices of an edge  ≡  endpoints of the edge.
3. edge {x, y}  ≡  join x and y  ≡  is incident on x and y

A vertex may belong to no edge, in which case it is not joined to any other vertex.

• undirected graph for distinguishing from a directed graph
• simple graph for distinguishing from a multigraph
• wp/Bipartite_graph

grafo orientato, grafo diretto, digrafo (contrazione), directed graph, digraph

G = (V, A)

• V is a set whose elements are called vertices, nodes, or points;
• A ⊆ VxV is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

Un grafo orientato e' isomorfo a una relazione sull'insieme dei vertici; possiamo dire che e' un modo di illustrare graficamento la relazione.

dim: R ⊆ XxY relazione binaria tra 2 insiemi X e Y.

R ⊆ XxX relazione binaria in un insiemi X. 

Confrontato con  G = (V, A), notiamo A ⊆ VxV ;  R ↔ A  e  X ↔ V

edge e vertice sono i 2 elementi costituienti un grafo:

• edge has 2 vertices to which it is attached, called its endpoints

nodes = vertex

loop : an edge that join a vertex to itself. It forms a cycle of length 1.

parallel edges : join the same vertices

simple edge : no parallel edges.

simple graph : no loops, no parallel edges; each edge connects distinct endpoints and no two edges have the same endpoints.

In many cases, graphs are assumed to be simple unless specified otherwise.

simple path or simple cycle : a path or cycle that has no repeated vertices and consequently no repeated edges.

length of a cycle, path, or walk is the number of edges it uses.

vertici adiacenti    uniti da un arco

archi adiacenti      vertice in comune

Handshaking lemma

degree of a vertex in a graph: the number of its incident edges.

(in an undirected graph) the sum of the degrees of all vertex  equals twice the number of edges.

dim: 1 edge ↔ +2 degree.  Iniziando dall'insieme vuoto, questa regola vale sempre.

path Path_(graph_theory)

a sequence of edges which joins a sequence of distinct vertices, exept

closed path : same first and last vertex.

Since the vertices are distinct but 1, so are the edges.

walk : vertici con possibili ripetizioni.

trail : vertici distinti

Grafo wikipedia

1. Glossary_of_graph_theory
2. Graph_(mathematics)

   Graph_theory  |  Glossary_of_graph_theory

3. Planar_straight-line_graph, straight-line graph
4.  
5. Directed_graph
6. Directed_acyclic_graph | Partial_order | Order_theory | Ordered_set
7.  
8. Cyclic_order
9. Hierarchy
10. Keller's_conjecture | Clique_(graph_theory)  cricca

Extremal combinatorics > extremal graph theory

es: if a graph has n vertices, then how many edges can it have without any three of them forming a triangle?

In general, questions in extremal combinatorics ask

• how big some quantity can be before something else is forced to happen.

Szemerédi's theorem itself is another example:

how many numbers you can choose between 1 and n before you are forced to include an arithmetic progression of length k.

gowers/pdf The work of Endre Szemerédi, Abel price 2012

GEGL GenericGraphicsLibrary > Non-destructive_editing > Generation_loss