Sem trabalhos

Grafos simples: Denotado por G = (V, E) onde V de vértice e E de arestas, onde as arestas são interconexos (linhas) dos vértices (pontos) de um grafo.

|V(G)| = n = Número de vértices. |E(G)| = m = Número de arestas.

Multigrafo: composto também por arestas paralelas (mais de uma aresta para dois vértices), laços (arestas com incidencia inicial e final no mesmo vértice).

Vizinhança ou adjacencia : Um vértice e vizinho de outro quando há interligação através de alguma aresta. Representado por N(v) = {w pertence V | (v, w) pertence E}

Vértice isolado: Quando o vértice não tem interligação com aresta. N(v) = 0

Vértice univesal: Quando um vértice é vizinho de todos os outros vértices do grafo. N(v) = V-{v}.

Complemento de um grafo: Denotado por G. Grafo com mesmo conjunto de vértices de G, sendo que os vértices adjacentes em G não sejão adjacentes em G e virce e versa.
V(G) = V(G) e E(G) = {(v,w) | v, w pertence V(G) e (v, w) ñ pertence E(G)}

Subgrafos. Representação parcial de um grafo, onde H é subgrafo de G se V(H) C V(G) e E(H) C E(G), então é um subgrafo.

Subgrafo Induzido: Onde o subgrafo contém todas as arestas do sub-conjunto de vértices induzido
Onde o subconjunto de vétices AC V(G) e
V(H) = V(G[A])=A e E(H)=E(G[A])={(x,y) E E(G)|x E A e y E A}

Subgrafo Gerador: Onde o subgrafo contém todas os vértices do grafo, onde V(H) =V(G)

Grafo completo (K): Grafo onde todos os vértices são adjacentes aos demais vértices.
Representado por K(maiúsculo). Exemplo o K1 o--------------o K2

Clique: Subgrafo A de G onde forma um grafo completo. Onde (A C V(G)). A é um clique de G se G[A] é um grafo completo.

Grafo nulo ou independente: se não há vértices adjacentes. Denotado de Nn. Exemplo N1 O
Conjunto independente: Subconjunto de vértices de G (S C V(G)), onde não há adjacencia entre os vértices.

Grau de um vértice: É o número de arestas incidentes em v. Denotado por d(v). d(v)=|N(v)|=|{w C V| (v,w) C