^^Grafo.

graph (undirected)

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

punti e linee sono i 2 elementi costituenti un grafo

points ≡ nodes ≡ vertices; point ≡ node ≡ vertex
lines ≡ links ≡ edges
edge {x, y} ≡ join x and y ≡ is incident on x and y
vertices of an edge ≡ endpoints of the edge.
edge has 2 vertices to which it is attached, called its endpoints

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

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.

arc ≡ arrow ≡ directed line

possiamo dire che un grafo e' un modo di illustrare graficamento la relazione.

dim: rem: 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

punto isolato non incide con nessuna linea, non e' collegato con nessun altro punto
vertici adiacenti uniti da un arco
archi adiacenti vertice in comune
loop an edge that join a vertex to itself. It forms a cycle of length $1.$
parallel edges join the same points
simple edge no parallel edges.
simple graph simple edges and no loops
- no loops ⇔ each edge connects distinct endpoints
- no parallel edges, no two edges have the same endpoints.
simple graph distinguishing from multigraph

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.

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.

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

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

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