4.5: Introducción a la Teoría de las Gráficas

Podemos interpretar el problema sdr como un problema sobre las gráficas. Dados conjuntos\(A_1,A_2,\ldots,A_n\), con\(\bigcup_{i=1}^n A_i=\{x_1,x_2,\ldots,x_m\}\), definimos una gráfica con\(n+m\) vértices de la siguiente manera: Los vértices están etiquetados\(\{A_1,A_2,\ldots,A_n,x_1,x_2,\ldots x_m\}\), y los bordes son\(\{\{A_i,x_j\}\mid x_j\in A_i\}\).

Ejemplo\(\PageIndex{1}\)

Vamos\(A_1=\{a,b,c,d\}\),\(A_2=\{a,c,e,g\}\),\(A_3=\{b,d\}\), y\(A_4=\{a,f,g\}\). La gráfica correspondiente se muestra en la Figura\(\PageIndex{1}\).

Figura\(\PageIndex{1}\): Un sistema de conjunto representado como una gráfica bipartita.

Antes de explorar esta idea, introducimos algunos conceptos básicos sobre las gráficas. Si dos vértices en una gráfica están conectados por un borde, decimos que los vértices son adyacentes. Si un vértice\(v\) es un punto final de borde\(e\), decimos que son incidentes. El conjunto de vértices adyacentes a\(v\) se llama el barrio de\(v\), denotado\(N(v)\). Esto a veces se le llama el barrio abierto de\(v\) para distinguirlo del barrio cerrado de\(v\),\(N[v]=N(v)\cup\{v\}\). El grado de un vértice\(v\) es el número de aristas que inciden con\(v\); se denota\(\text{d}(v)\).

Some simple types of graph come up often: A path is a graph \(P_n\) on vertices \(v_1,v_2,\ldots,v_n\), with edges \(\{v_i,v_{i+1}\}\) for \(1\le i\le n-1\), and no other edges. A cycle is a graph \(C_n\) on vertices \(v_1,v_2,\ldots,v_n\) with edges \(\{v_i,v_{1+(i\bmod n)}\}\) for \(1\le i\le n\), and no other edges; this is a path in which the first and last vertices have been joined by an edge. (Generally, we require that a cycle have at least three vertices. If it has two, then the two are joined by two distinct edges; when a graph has more than one edge with the same endpoints it is called a multigraph. If a cycle has one vertex, there is an edge, called a loop, in which a single vertex serves as both endpoints.) The length of a path or cycle is the number of edges in the graph. For example, \(P_1\) has length 0, \(C_1\) has length 1. A complete graph \(K_n\) is a graph on \(v_1,v_2,\ldots,v_n\) in which every two distinct vertices are joined by an edge. See Figure \(\PageIndex{2}\) for examples.

Figure \(\PageIndex{2}\): Graphs \(P_5\), \(C_6\), \(K_5\).

The graph in Figure \(\PageIndex{1}\) is a bipartite graph.

Definition \(\PageIndex{1}\): Bipartite

A graph \(G\) is bipartite if its vertices can be partitioned into two parts, say \(\{v_1,v_2,\ldots,v_n\}\) and \(\{w_1,w_2,\ldots,w_m\}\) so that all edges join some \(v_i\) to some \(w_j\); no two vertices \(v_i\) and \(v_j\) are adjacent, nor are any vertices \(w_i\) and \(w_j\).

The graph in Figure \(\PageIndex{1}\) is bipartite, as are the first two graphs in Figure \(\PageIndex{2}\).

Contributors and Attributions

• Template:ContribGuichard