👋🏼 Presentación

https://github.com/algoritmos-rw/tda_ejemplos

En un examen no se espera una demostración formal, pero en un TP si (completa).

🔢 Inducción matemática

$(H \implies T) = (\neg H \lor (H \land T))$

$H$	$T$	$H \implies T$
F	V	V
F	F	V
V	V	V
V	F	F

Métodos de demostración

Directo: asumimos que la hipótesis es verdadera y demostramos que la tesis también lo es.
Contrarrecíproco: demostramos por método directo que $\lnot T \implies \lnot H$.
Absurdo/Contradicción: suponemos que la hipótesis es verdadera y la tesis es falsa, y llegamos a una contradicción. Básicamente es para descartar el último caso de la tabla de verdad, que es el único caso en el que el enunciado es falso.
Inducción: para demostrar una proposición $P(\mathbb{N}^0)$, empezamos probando el caso base (demostrar $P(n_0)$) y luego hacemos el paso inductivo (lo demostramos para el siguiente) (demostramos $P(n_{0+1})$). Con eso, podemos decir que $\forall h \geq n_0, v[P(h) \implies P(h+1)]] = \mathbb{V}$.

✡️ Propiedades matemáticas de grafos

Matriz de adyacencia

Propiedades:

Es cuadrada ($V \times V$)
Si es un grafo no dirigido $\implies$ es simétrica
Si el grafo no tiene bucles $\implies$ la diagonal son todos ceros

Teorema de potenciación: siendo $A$ la matriz de adyacencia de un grafo $G$ $\implies$ $A{^n}_{ij}$ nos indica la cantidad de caminos de largo $n$ de $i$ a $j$.

Árbol

Sea $V$ el conjunto de vértices de $G$, un árbol es un grafo no dirigido $/ \ \forall v,w \isin V, \exist ! camino(v,w)$.