--- 
title: Resumen Parcial 1
author: Federico Polidoro
---

# Clase 1
## Grafos
Los grafos pueden ser descriptos como Graficos compuestos por nodos y vertices que conectan dichos nodos. Tales Vertices pueden o no ser Dirijidos.

## Grados
Estos consisten en el numero de la cantidad de aristas a la que esta conectado un vertice o nodo. Pero en el caso de un grafo dirijido vamos a tener un grado de entrada y otro de salida los cuales se cuentan de forma individual las aristas que llegan o salen de ese nodo.

## Ciclos
Es cuando una arista va de un vertice al mismo vertice.

## Tipos de Grafos
Existen diferentes tipos de grafos estos son:
- Dirijido  
    Es un Grafo en el cual las aristas tienen una direccion predefinida.

- Completo
    Es un Grafo donde todos los vertices estan interconectados entre si directamente.

- Ciclo
    Es un Grafo donde todos los vertices estan conectados de forma secuencial por ejemplo el a-b-c-d-al Similar al token ring.

- Rueda
    Este es como el Grafo ciclo pero hay un nodo extra que esta conectado en el centro con los demás.

- Estrella
    Este es similar a como funciona el 802.11 donde todos los vertices estan directamente conecrados con un vertice central.

- Regular
    Es un Grafo donde todos los vertices tienen el mismo grado.

- Conexo
    Es un Grafo donde no hay vertices sueltos sino que es posible crear un camino de cualquier vertice a cualquier otro.

## Matrices
### Adyacencia
Siempre es cuadrada e contiene una relacion entre los vertices y con cuales estan relacionados  
Por ejemplo en un triangulo.

|   | A | B | C |
| A | 0 | 1 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 1 | 0 |

### Incidencia
Una matriz de incidencia tiene la relacion entre el vertice y la arista volviendo al ejemplo  

|   |e1 |e2 |e3 |
| A | 1 | 1 | 0 |
| B | 0 | 1 | 1 |
| C | 1 | 0 | 1 |

En esa tabla se ve que la arista 1 se conecta entre el nodo a y c, la 2 con a y b y la 3 con b y c. Dado que el ejemplo queria mostrar un triangulo.

# Clase 2
## Grafo Plano
Este es un grafo el cual sus aristas no se cortan entre si al momento de la graficacion. Se puede re ubicar todos los componentes mientras no se alteren sus relaciones, para poder mostrar si es plano o no.

## Arboles	
Consiste de un Grafo Conexo sin ciclos. Existe un tipo de arbol dirijido conocido como arbol con raiz

# Clase 3
## Arboles Recubridores
En un marco teorico en el cual necesitas conectar todos los vertices usando la menor cantidad de conexiones posibles lo que estas buscando es una estructura de arbol. Un Arbol recubridor se puede observar en grafos como un subgrafo con forma de arbol y que contiene todos los vertices del grafo dado.

## Minimales
Para ciertas aplicaciones interesa conocer el arbol recubridor de peso minimo, dandole un peso a cada union lo que busca es uno el cual tenga el menor costo de intalacion. (no se si me explico). Tambien existen los maximales que son literalmente lo opuesto.

## Busqueda de Profundidad
Es un algoritmo de busqueda en el cual se empieza elijiendo los nodos más superficiales ( a -> b -> c )
una vez que llegamos al final volvemos para arriba 1 nodo a la vez buscando si hay algun nodo que no hayamos encontrado para ir hacia ese en caso de no haberlo vamos 1 más para arriba

## Busqueda a lo Ancho
Es un algoritmo que intenta recorrer todos los nodos posibles lo que hacemos es tener dos arrays de nodos vistos y lo que hacemos es que primero añadimos los nodos que estan directamente conectados con el nodo que estamos parados al array de nodos vistos y añadimos el nodo en el que estamos parados al array de recorrido. Lo que sigue es ir al siguiente nodo y hacer lo mismo hasta llegar a nuestro destino final. El criterio para recorrer los nodos es que agarramos los que son más cercanos en numero de saltos al nodo inicial primero.

# Clase 4
## Recurrencias
El concepto de la recurrencia viene de lo que en matematicas se llama una sucesion, es decir, un conjunto ordenado de numeros. 

# Clase 5 
## Recurrencias Lineales
El ejemplo que se da en la clase es un: $a_n = c * a_{n-1}$ donde c es un coeficiente constante

## Primer orden
son las que el offset es de 1 $\pm$

## Segundo orden 
es cuando la diferencia entre los offset es 2 $\pm$ . Entre el qde menor offet y el de mayor.

# Clase 6
## Recurrencias No Homogeneas
Una recurrencia no homogenea es cuando dentro de la secuencia esta contiene un elemento el cual no depende de la recurrencia por ejemplo un 

$a_n = 2a_{n-1} + 3n$

No es Homogenea mientras que un 

$a_n = 2a_{n-1}$

Si lo es, y si quisiera hacer esta ultima en una no homogenea podria hacer:

$a_n = 3a_{n-1} + 3n$ 

# Clase 7
## Enteros Divisibilidad
Se puede decir que un numero A es divisible por B y tambien por -B, o que B es multiplo de A. 

## Primos 
De la primaria sabemos que un numero primo es tal que solo puede dividirse por $\pm$ si mismo o $\pm$ 1 y todos los que no cumplen con eso son conocidos como **Compuestos**.

## Teorema de la Aritmetica 
Todo numero entero mayor a 1 se puede escribir como producto de numeros primos en forma unica.

## Nota

- MCD,
   Maximo comun Divisor

- MCM,
   Minimo comun Multiplo


	
