https://sites.icmc.usp.br/aurichi/comb/ 2026-05-06T14:56:17-0300 https://sites.icmc.usp.br/aurichi/comb/ https://sites.icmc.usp.br/aurichi/comb/lib/tpl/dokuwiki/images/favicon.ico text/html 2020-03-17T10:42:47-0300 Anonymous (anonymous@undisclosed.example.com) https://sites.icmc.usp.br/aurichi/comb/doku.php?id=lista:arvores&rev=1584452567&do=diff Árvores Fazer a lista de conexidade será bem proveitoso. Dizemos que um grafo $T = (V,A)$ é uma floresta se não possui ciclos como subgrafos. Uma floresta conexa é dita ser uma árvore. Observe o grafo cujo conjunto de vértices corresponde aos pontos pretos abaixo e cujas arestas estão todas representadas. Esse grafo é uma floresta? Ele possui uma floresta como subgrafo? Mais do que isso, ele possui uma floresta como subgrafo induzido? Alguma de suas componentes conexas é uma árvore? Se sim,… text/html 2020-03-03T08:43:57-0300 Anonymous (anonymous@undisclosed.example.com) https://sites.icmc.usp.br/aurichi/comb/doku.php?id=lista:basico&rev=1583235837&do=diff Grafos - Definição e exemplos básicos 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$$G$$V_G$$A_G$$v, w$$\{v, w\}$$v$$N(v) = \{w: w$$v\}$$N$$g(v) = |N(v)|$$v$$G$$\delta(G) = \min\{d(v): v \in V_G\}$$\Delta(G) = \max\{d(v): v \in V_G\}$$v$$w$$G$$n$$K_n$$K_n$$G$$G = (V,A)$$\bar{G} = (V,A')$$\{x… text/html 2020-03-20T09:56:00-0300 Anonymous (anonymous@undisclosed.example.com) https://sites.icmc.usp.br/aurichi/comb/doku.php?id=lista:bipartidos&rev=1584708960&do=diff Grafos Bipartidos Algumas definições e alguns resultados das listas de conexidade e de árvores serão utilizados. Dizemos que um grafo $G = (V,A)$ é um grafo bipartido se existirem $V_1,V_2\subset V$ tais que $V = V_1 \cup V_2$, $V_1\cap V_2 = \emptyset$ e, dada $\{a,b\}\in A$ uma aresta, tem-se que $a\in V_1$ e $b \in V_2$ ou $b\in V_1$ e $a \in V_2$. Nesse caso, $\{V_1,V_2\}$ é chamada bipartição$G$$G = (V,A)$$\{V_1,V_2\}$$\{V_1',V_2'\}$$G$$V_1 = V_1'$$V_2 = V_2'$$V_1 = V_2'$$V_2 = V_1'$$G =… text/html 2020-02-29T17:56:00-0300 Anonymous (anonymous@undisclosed.example.com) https://sites.icmc.usp.br/aurichi/comb/doku.php?id=lista:caminhosciclos&rev=1583009760&do=diff Caminhos e ciclos Um caminho é uma sequência $\langle v_1, \ldots, v_n\rangle$ de vértices onde cada $\{v_i, v_{i + 1}\}$ é uma aresta (todas as arestas são distintas). Um caminho é dito simples se cada vértice aparece no máximo uma vez. O comprimento de um caminho é a quantidade de arestas deles (ou seja, $n$$G$$\delta(G)$$\langle v_1, \ldots, v_n, v_{n + 1}\rangle$$v_{n + 1} = v_1$ text/html 2020-03-17T10:42:24-0300 Anonymous (anonymous@undisclosed.example.com) https://sites.icmc.usp.br/aurichi/comb/doku.php?id=lista:conexidade&rev=1584452544&do=diff Conexidade Fazer a lista de caminhos e ciclos pode ajudar. Dizemos que um grafo $G = (V,A)$ é conexo se, dados $x,y\in V$ vértices do grafo, existir um caminho $\langle v_1,v_2,\dots,v_n\rangle$ de $G$ com $v_1=x$ e $v_2=y$. Nessas condições, dizemos que $\langle v_1,v_2,\dots,v_n\rangle$ conecta ou liga os vértices $x$ e $y$. O comprimento do menor caminho ligando esses dois vértices é dito ser a $x$$y$$d(x,y)$$x=y$$d(x,y)=0$$x,y \in V$$G$$d(x,y) = \infty$$n$$K_n$$G$$\delta(G) = 1$$\Delta(G) … text/html 2020-03-25T11:34:44-0300 Anonymous (anonymous@undisclosed.example.com) https://sites.icmc.usp.br/aurichi/comb/doku.php?id=lista:kuratowski&rev=1585146884&do=diff Teorema de Kuratowski Dizemos que um grafo $G = (V,A)$ é uma subdivisão de um grafo $H = (V',A')$ se $G$ é construído a partir da remoção de uma quantidade finita de arestas de $H$ e a substituição de cada uma dessas arestas por caminhos conectando seus vértices. No exemplo abaixo, o grafo $G$$H$$H$$K_{3,3}$$K_5$$K_{3,3}$$K_5$$G=(V,A)$$G$$v\in V$$V\setminus \{v\}$$v$$G$$H$$G$$H'$$G$$H$$H'$$H=H'$$G$$G = (V,A)$$u,v \in V$$d(u,v)$$G$$u$$v$$G$$G$$G$$H$$H'$$H$$H'$$G$$C$$B$$T$$C\cup B$$\{c,b\}$$c \… text/html 2020-03-25T11:47:50-0300 Anonymous (anonymous@undisclosed.example.com) https://sites.icmc.usp.br/aurichi/comb/doku.php?id=lista:planares&rev=1585147670&do=diff Grafos Planares Algumas definições e alguns resultados das listas de conexidade e de árvores serão utilizados. Dizemos que um grafo $G = (V,A)$ é um grafo planar se ele pode ser desenhado no plano de modo que suas arestas não se intersectam. Tal desenho será designado representação planar$G = (V,A)$$\{R_1,R_2,\dots,R_n\}$$b(R_i)$$R_i$$\displaystyle \sum_{i=1}^nb(R_i) \leq 2|A|$$G$$G$$b(R)$$R$$G$$n$$q$$r$$n-q+r=2$$G$$q=0$$G$$q$$G$$G = (V,A)$$|V|\geq 3$$|A|\geq 3$$|A|\leq 3|V|-6$$K_5$$G$$12$$\de…