Combinando

===== Grafos - Definição e exemplos básicos =====

<WRAP info>
Um grafo é um par de conjuntos $G = (V, A)$ onde os elementos de $V$ são chamados de **vértices** e os elementos de $A$ são pares de elementos de $V$ (este par pode ou não ser ordenado). Os elemetos de $A$ são chamados de **arestas**. Quando os elementos de $A$ são ordenados, dizemos que o grafo é **orientado**. 
</WRAP>

<WRAP tip>
A menos de menção contrária, quando dizemos grafo, estamos nos referindo a um grafo não orientado, com finitos vértices, sem **loops** (uma aresta formada por um único vértice) e sem arestas paralelas (todos as arestas são distintas).
</WRAP>

<WRAP tip>
Quando fixamos um grafo $G$, sem mencionar quem são seus vértices e arestas, muitas vezes vamos usar a notação $V_G$ e $A_G$ para tais conjuntos respectivamente.
</WRAP>

{{ :lista:exemplobasico.png?600 |}}

<WRAP tip>
Normalmente representamos um grafo como acima: os vértices são os pontos e as arestas são as linhas conectando tais pontos.
</WRAP>

<WRAP info>
Dizemos que dois vértices $v, w$ são **adjacentes** se $\{v, w\}$ é uma aresta. Dado um vértice $v$, dentamos por $N(v) = \{w: w$ é adjacente a $v\}$ ($N$ de neighbor). Finalmente, denotamos por $g(v) = |N(v)|$ (**grau** de $v$). 
</WRAP>


**~~#~~** Mostre que a soma de todos os graus de todos os vértices de um grafo é par.

**~~#~~** Mostre que o total de vértices de grau ímpar é par.

**~~#~~** Mostre que todo grafo possui dois vértices de mesmo grau.

<WRAP info>
Dado um grafo $G$, denotamos por $\delta(G) = \min\{d(v): v \in V_G\}$ e por $\Delta(G) = \max\{d(v): v \in V_G\}$. 
</WRAP>

<WRAP info>
Dizemos que um grafo é **completo** se dados quaisquer $v$ e $w$ vértices distintos, temos que eles são adjacentes. Se $G$ tem $n$ vértices e é completo, o denotamos por $K_n$.
</WRAP>

**~~#~~** Quantas arestas tem $K_n$?

<WRAP info>
Dado $G$ um grafo, definimos o grafo **complementar** de $G = (V,A)$, denotado por $\bar{G} = (V,A')$, da seguinte maneira: $\{x,y\}\in A'$ se, e somente se, $\{x,y\}\notin A$.
</WRAP>

<WRAP info>
Dados $G = (V_G, A_G)$ e $H = (V_H, A_H)$ grafos, dizemos que $H$ é um **subgrafo** de $G$ se $V_H \subset V_G$ e $A_H \subset A_G$. Se, além disso, toda aresta ${v, w} \in A_G$ com $v, w \in V_H$ for tal que $\{v, w\} \in A_H$, dizemos que $H$ é um **subgrafo induzido**.  
</WRAP>

**~~#~~** Dê um exemplo de um subgrafo que não seja um subgrafo induzido.
Combinando

User Tools

Site Tools

Page Tools
