Árboles

Un árbol es un grafo conexo sin ciclos.
Árboles con raíz : un árbol con raíz "r"  (a "r" llamaremos raíz del árbol). Existe una única trayectoria de r a cualquier otro vértice "v", esto da una dirección a los arcos de r. La longitud de la trayectoria que va de r a v se   llama nivel o profundidades de "v"(vértice). Aquellos vértices con grado uno distintos de "r", se llaman hojas del árbol con raíz. Una trayectoria  dirigida de un vértice a una hoja se llama rama.
ejemplo:

la figura de arriba es un árbol con raíz "r". Este árbol tiene 5 hojas: d,f,h,i y j. El nivel de "a" es 1, el nivel de "f" es 2 y el nivel de "j" es 3. Cualquier árbol puede convertirse en un árbol con raíz eligiendo simplemente uno de sus vértices como raíz.

¿para que sirve un árbol con raíz?.

Un árbol con raíz es una ayuda útil para enumerar todas las posibilidades lógicas de una sucesión de sucesos  donde cada suceso  puede ocurrir de un numero finito de maneras.

Instituto Tecnologico de Apizaco.

Autor: Elizabeth Sola Lira.

Automatas de estado finito

View more presentations from ElizabethSola.

Grafos planos, formula de Euler y Teorema de Kuratowski.

Un grafo o multigrafo que se puede dibujar en el plano sin que se crucen sus arcos se llama plano. Aunque el grafo completo de K4 se suele dibujar con arcos que se cruzan como en la figura 6.1(a), también se puede dibujar sin que se crucen sus arcos como en la figura 6.1(b). Luego K4 es un grafo plano.

Formula de Euler: Euler dio una formula que relacionaba el numero de V de vértices, el numero E de arcos y el numero R de regiones de un mapa conexo. V-E+R=2. Es muy importante que el grafo correspondiente al mapa sea conexo, pues en caso contrario la formula no es cierta. En la siguiente figura tenemos  V=6, E=9 y R=5 y como afirma la formula de euler: V-E+R=6-9+5=2.

Teorema de Kuratowski:Un grafo es no plano si y solo si contiene un subgrafo homeomorfo a K3,3 o K5.

 

Intituto Tecnologico de Apizaco.

Autor: Elizabeth Sola Lira

Técnicas de Conteo.

Las técnicas de conteo son aquellas que son usadas para enumerar eventos difíciles de cuantificar.

Estas técnicas de conteo tienen como objetivo las combinaciones, estas se forman a través de 2 condiciones: con repetición y sin repetición, se pueden visualizar en forma de árboles,grupos y matriz (arreglo).********************************************************************

Empezaremos por explicar en que consiste el teorema fundamental de la multiplicación y de la adición..****

*********************************************************************************

Teorema Fundamental de la multiplicación: Si una combinación se quiere establecer de "n formas" y cada una de ellas se puede llevar a cabo de "m maneras distintas" en una segunda operación. Entonces se dice que juntas las operaciones pueden realizarse: nxm.*******************************************

Ejemplo:*************************************************************************

Se desea conocer el número de placas que se pueden formar si estas tienen 2 dígitos y 3 letras mayúsculas. Establecer de cuantas maneras se pueden formar sin repetición y con repetición.*********************

Datos***************************************************************************                                   Dígitos (D) = 10********************************************************                       

Letras mayúsculas (L)=27*************************************************************

Desarrollo************************************************************************
a)con repetición  DDLLL =   10X10X27X27X27 = 1,968,300  maneras.``````````````````````                        b)sin repetición* DDLLL=10x9x27x26x25=1,579,500 maneras.********************************
***********************************************************************************
Teorema Fundamental de la Adición: Si un evento se puede llevar a cabo de "n o m lugares distintos", además de no ser posible que se lleve a cabo el mismo evento o dos lugares distinto al mismo tiempo. Entonces el evento se puede realizar: n+m formas diferentes.********************************
Ejemplo**********************************************************************
Supóngase que se desea etiquetar las gavetas de los alumnos de la primaria, y que la etiqueta puede estar marcada con un solo digito, una sola letra o la combinación de una sola letra con un solo digito (sin importar si primero se pone la letra y después el digito o al contrario.  *************************Bajo estas condiciones , el numero de etiquetas distintas que se pueden formar son:pppppppppppppppppp
Datos*****************************************************************************
D=10*****************************************************************************
L=27*****************************************************************************
Desarrollo***************************************************************************
Etiquetas= D+L+D*L+L*D al sustituir queda:**********************************************
Etiquetas=10+27+10*27+27*10*********************************************************
Etiquetas=577**********

Instituto Tecnologico de apizaco.

Autor: Elizabeth Sola Lira.

**************************

Bienvenido a:

ocurrencias-matedis.blogspot.com. Es un sitio web que recopila textos o artículos referente a la materia de Matemáticas Discretas, con el fin de aportarte conocimientos de manera ingeniosa.