Lista 1 - Comunicação e Redes - UFABC

Prévia do material em texto

Lista 1 – Comunicação e Redes 2021.1 – UFABC
Aritanan Gruber
aritanan.gruber@ufabc.edu.br
http://professor.ufabc.edu.br/∼aritanan.gruber
1. I ♠ Balls and bins. Quantas possibilidades existem para se distribuir k reais entre n pessoas de forma
que cada uma receba ao menos um real? Suponha agora que não é necessário às pessoas
receberem ao menos um real. Qual o número de diferentes formas de distribuição neste caso?
Resposta: As possibilidades existentes para que n pessoas recebam pelo menos 1 real seria a
distribuição de (k - 1) moedas, como k > 0, temos que o número de vetores irá ser (x1,.…., xn) = K e
temos que como a última pessoa não deve influenciar a distribuição, já que ela que ficará com as
moedas em demasia, serão então (n - 1) pessoas. Logo, todo Xi terá que ser ≥ 1∀ i = 1, ……, n ,
Assim o número de maneiras possíveis de distribuição de moedas será uma relação:
No caso em que não é necessário a pessoa receber pelo menos 1 real, a fórmula será:
2. Packing. Alice deseja enviar sete soluções químicas a Bob: A, B, C, D, E, F e G. No entanto, qualquer
par de soluções dentre A, B, C e G não podem ser acondicionadas numa mesma caixa, pois podem
reagir entre si e causar explosões. Além disso, A e F reagem com D ou E. Alice deseja enviar todas as
soluções no menor número possível de caixas – pois ela pagará por caixa enviada. Modele o
problema que Alice deseja resolver com um grafo e determine o menor número de caixas que ela
deve utilizar. Justifique sua resposta.
Resposta:
- A, B, C e G não podem estar na mesma caixa
- A e F reagem com D ou E
Total de soluções químicas = 7
Sendo 7 soluções químicas, das quais 4 não podem ser misturadas entre si, mas podem estar em
contato com as outras 3 soluções, temos outra condição de A e F reagem com D ou E, temos as
seguintes possibilidades de combinações:
http://professor.ufabc.edu.br/%E2%88%BCaritanan.gruber
Obs: considerei que D pode reagir com E
As escolhas de combinações entre essas, impactará as outras combinações nas caixas, podendo
formar três pares (1 ficará sozinha), portanto, o menor número de caixas será 4.
3. Regularity. Um grafo é k-regular se todos os vértices possuem grau igual a k. Seja {R, S} uma bipartição
de um grafo k-regular G. Mostre que se k > 0 então |R| = |S|.
Temos um grafo bipartido, ou seja, um vértices contido em |R| devem estar conectado com um vértice
em |S| , temos também que o grafo é regular devendo satisfazer que o grau de entrada e o grau de
saída de cada vértice sejam iguais uns aos outros, nesse caso K > 0. Como todos os vértices estão
ligados ( podendo apenas estar ligado com os elementos do outro conjunto), deve existir o mesmo
número de arestas em cada conjunto e o mesmo número de vértices. |R| = |S|
4. Double counting. Prove as seguintes generalizações da identidade de Euler (handshaking lemma):
A) é a somatória dos graus dos vértices de X, representa também o número de
arestas que incide em cada um deles (vértices)
quantas arestas tem um ponto em x. Sendo contada 2 vezes, se as duas pontas
estiverem em x
∴
B)
A matriz L = D - A
D = grau dos vértices
A = adjacência do grafo
L = Matriz
BBT = L
BBT = Matrizes de incidência (x, y) V x E e (x, y) V x V
L = matriz
Podemos assim verificar que existe uma equivalência entre BBT e D - A, sendo igual a matriz
laplaciana não normalizada
A) G é um grafo conexo
Se G tem n vértices, então ele (G) tem pelo menos n -1 arestas (m)
Para que esse grafo seja conexo é preciso que ele supra a condição de que |A(G)| ≥ n - 1
Para que o número de arestas não seja inexistente é preciso que n > 1
Podemos verificar isso utilizando a fórmula do número de arestas possíveis de um grafo:
m > n - 1 ( n - 2) / 2
⇾ m = n( n - 1) / 2 n( n -1)/2 > n - 1 (n - 2)/2
⇾ n > n - 2 ⇾ m = n > m = n - 2
Podemos ter duas condições:
- Um grafo não orientado e conexo ( com base nas propriedades acima), onde G ( V, A ) e que
G’ é um subgrafo, que permanecerá conexo ao ser inserido um novo Vértice, mas que faz-se
necessário inserir uma nova aresta não modificando a propriedade, mantendo M > (n - 2).
- E considerando N > 1, o número de arestas (m) para um grafo (que respeite as condições
citadas previamente), deve ser m > (n-2), assim teremos que sendo um grafo m = (n -2), ele
não é conexo.
B) G ( V, A) é um grafo não orientado e conexo com n vértices
n = 2k | k é inteiro e > 0
δ > ( 2k - 2)/2 ➝ δ > ( k -2).
Utilizando G (3,2), possuindo 3 vértices e duas arestas, é possível ver que δ = ½ (n - 2) é
verdadeira, já que 3 - 2 = 1, sendo assim o valor de k ou n devem ser tais que δ > 0
δ > (n-2)/2 δ = (n-2)/2
- D = (V, A) é um digrafo
- c : A ➝ [0,1]
- P é o conjunto de todos os caminhos orientados de D.
Quero determinar um P* que pertença a P
P* = argmaxP ∈ P c (P) = argmaxP ∈ P c(e)
e∊E(P)
Log de c(P*) e substituindo max por min , temos:
-log c(P*) = min ∑ Log 1 / c (e)
P ∊ P e∊E(P)
Vemos que Log 1 / c (e) ≥ 0 arco e ∊ A, pois C (e) ∊ [0, 1]. Ou seja, o lado direito da relação descrita
acima é estabelecida por um problema de determinação de caminhos mínimos entre todos os pares de
vértices de um digrafo sob distâncias não negativas: w(e) = log 1/c(e).