Membros

quinta-feira

Grafos e Matrizes de Adjacência (Parte 2)

Neste post, responderemos as duas perguntas que foram apresentadas na parte 1 o qual reproduzimos abaixo:

[;i);] Quais os vértices que estão conectados por uma sequência de dois lados?
[;ii);] Quantas sequências distintas de dois lados conectam cada par de vértices?

Considere a figura acima. Os vértices [;B;] e [;F;] estão conectados por duas sequências de dois lados ([;BCF;] ou [;BEF;]). Note que os dois lados entre [;B;] e [;C;] são indistinguíves.

Seja [;m_{ij};] a [;(i,j);] entrada na matriz de adjacência [;M;]. Note que

[;m_{21}m_{16} + m_{22}m_{26} +m_{23}m_{36} + m_{24}m_{46} + m_{25}m_{56} + m_{26}m_{66} =;]
[; = 1\cdot 0 + 0\cdot 0 + 1\cdot 1 + 0\cdot 0 + 1\cdot 1 + 0\cdot 1 = 2;]
o qual é o número de sequências de dois lados entre [;B;] e [;F;]. Note que, desde que [;B;] conecta com [;C;] e [;C;] com [;F;], [;m_{23}m_{36} = 1;]; desde que [;B;] conecta com [;A;] e [;A;] não conecta com [;F;], [;B;] não conecta com [;F;] através de [;A;] com uma sequência de dois lados, por isso, [;m_{21}m_{16} = 0;]. Somando todos os pontos intermediários temos o resultado. 

Agora note que 
[;\sum_{k=1}^{6}m_{2k}m_{k6};]
é a entrada [;(2,6);] da matriz [;M^2;].

Observação 1: O número de sequências de dois lados entre o vértice [;i;] e o vértice [;j;] em um grafo com matriz adjacência [;M;] é a entrada [;(i,j);] na matriz [;M^k;]. Se [;M;] é a matriz adjacência para a figura acima, então
e
Portanto, existe uma sequência de dois passos (lados) de [;C;] a [;F;], e existem [;5;] sequências de [;3;] passos entre [;C;] e [;F;]. Observando a figura abaixo, 


As iniciais acima representam as seguintes cidades:
B = Boston
H = Hyannis
M = Martha`s Vineyard
Na = Nantucket 
Ne = New Bedford
P = Providence
Pr = Provincetown

vemos que Nantucket é conectada em duas etapas a partir de Boston (via Hyannis ou Martha's Vineyard), mas observe que existe um vôo direto entre as duas cidades. Assim, temos a seguinte pergunta:

Qual é o menor número de arestas (lados) que devem ser percorridos para ir de um vértice [;A;] para um vértice [;B;]? 

Para responder esta questão, considere a matriz 
[;S_k = M + M^2 + \ldots + M^k;]

A [;(i,j);] entrada nesta matriz fornece o número de maneiras de interligar o vértice [;i;] ao vértice [;j;] em [;k;] passos ou menos. Se tal viagem é impossível, esta entrada será zero. Portanto, para encontrar o menor número de passos entre os vértices continue calculando [;S_k;] à medida que aumenta [;k;], o primeiro [;k;] para o qual a entrada [;(i,j);] em [;S_k;] é diferente de zero é o menor número de passos entre [;i;] e [;j;]. 

Outra questão referente a um grafo é se é possível ir de um vértice a qualquer outro. Se um grafo possui a propriedade de que cada vértice está ligado a todos os outros em um determinado número de passos dizemos que ele está conectado.

Como podemos determinar se um grafo está conectado?

Isso é fácil de ver se o grafo é pequeno. Mas é mais difícil de ver a partir da matriz de adjacência. No entanto, existe um cálculo que pode ser feito. 

Suponha que o grafo possui [;n;] vértices. Então o maior número de passos que poderia tomar para ir de um vértice para qualquer outro é [;n;] passos. Assim, 

[;S_n = \sum_{k=1}^{n}M^k;]


pode nos ajudar. Se houver qualquer zero nesta matriz será impossível conectar um par de vértices e portanto, o grafo não está conectado.

Gostará de ler também:
- Grafos e Matrizes de Adjacência (Parte 1);
- Matrizes (Parte 1);

sábado

O Valor Médio de uma Função

Uma das aplicações interessantes das integrais definidas além do cálculo da área de uma região curvilínea e do volume de um sólido de revolução, é determinar o valor médio de uma função sobre um intervalo [;[a,b];] . Esta grandeza já foi abordada no post Teoremas Relativos a Integral Definda (Parte 3) no qual foi apresentado o Teorema Fundamental do Cálculo. 

A forma apresentada foi através de uma definição, sem muita explicação que a expressão em termos de integral realmente está relacionada com uma média. Pensando sobre este assunto, apresentaremos neste post a média de uma função de uma forma construtiva.
Definição 1: Dado o conjunto de pontos [;\{y_1,y_2,\ldots,y_n\};], o valor médio denotado por [;VM;] é igual a soma desses números divididos por [;n;], ou seja,
[;VM = \frac{y_1 + y_2 + \ldots + y_n}{n} \qquad (1);]
Esta expressão é muito útil para valores discretos. Por exemplo, o valor médio do conjunto de pontos [;\{1.2,1.5,2.4,3.1\};] é [;VM = 2.05;]. Na Matemática e em outros campos da ciência aplicada, existem muitos modelos contínuos os quais precisamos calcular o valor médio. Deste modo surge a pergunta: 

Como calcular o valor de médio de um conjunto contínuo de pontos, tal como uma imagem de uma função contínua definida em um intervalo?

Para responder esta pergunta, seja [;f;] uma função contínua sobre o intervalo [;[a,b];]. Em seguida, dividimos [;[a,b];] em [;n;] subintervalos pelos pontos [;a = x_0,x_1,x_2,\ldots,x_n = b;]. Para facilitar o entendimento, suponhamos que os intervalos são uniformes. Deste modo, o comprimento de cada um deles é [;\Delta x = (b - a)/n;] conforme a figura abaixo. 
Tome um ponto [;\xi_1;] no subintervalo [;[a,x_1);], [;\xi_2;] em [;[x_1,x_2);] ou em geral, [;\xi_k;] no subintervalo [;[x_k,x_{k+1});] para [;k=0,1,\ldots,n-1;]. O valor médio de [;f;] no conjunto [;\{\xi_1,\xi_2,\ldots,\xi_n\};] de acordo com a expressão [;(1);] é:

[;VM = \frac{f(\xi_1) + f(\xi_2) + \ldots + f(\xi_n)}{n} = \frac{1}{n}\sum_{k=1}^{n}f(\xi_k);]
Sendo [;n = \frac{b - a}{\Delta x};], segue que
[;VM = \frac{1}{b - a}\sum_{k=1}^{n}f(\xi_k)\Delta x \qquad (2);]
Sendo [;f;] contínua, a medida que aumentamos o número de pontos, a expressão [;(2);] aproxima-se da integral definda de [;f;] sobre [;[a,b];]. Deste modo, definimos a valor médio de [;f;] sobre [;[a,b];] por 

[;VM(f) = \lim_{n \to \infty} VM = \lim_{n \to \infty}\biggl[\frac{1}{b - a}\sum_{k=1}^{n}f(\xi_k)\Delta x\biggr];]

[;= \frac{1}{b - a}\quad \lim_{n \to \infty}\sum_{k=1}^{n}f(\xi_k)\Delta x = \frac{1}{b - a}\int_{a}^{b}f(x)dx \qquad (3);]

Exemplo 1: Determine a temperatura média de uma estufa, sabendo que [;T(t);] é dada pela função 
[;T(t) = -\frac{t^2}{60} + \frac{t}{2} + 20 \qquad t \in [8,18];]

Resolução: Da expressão [;(3);] acima, temos

[;VM(T) = \frac{1}{18-8}\int_{8}^{18}\biggl(-\frac{t^2}{60} + \frac{t}{2} + 20\biggr)dt = 23,5^{\circ} \ C;] 

Teorema 1: Se [;f;] é uma função contínua em [;[a,b];], então existem [;\alpha;], [;\beta \in [a,b];] tal que [;f(\alpha) \leq f(x) \leq f(\beta);] para todo [;x \in [a,b];]. 

A prova envolve conceitos matemáticos sofisticados e portanto neste post, será omitida.  

Corolário 1: Se [;f;] é uma função contínua em [;[a,b];], existe [;c \in [a,b];] tal que [;VM(f) = f(c);]. 

Demonstração: Pelo teorema 1, existem [;\alpha, \beta \in \mathbb{R};] tais que [;m \leq f(x) \leq M;], seando [;m = f(\alpha);]  e [;M = f(\beta);]. Integrando esta desigualdades de [;a;] a [;b;], temos:


[;\int_{a}^{b}mdx \leq \int_{a}^{b}f(x)dx \leq \int_{a}^{b}Mdx \quad \Rightarrow;]
[;m(b - a) \leq \int_{a}^{b}f(x)dx \leq M(b - a) \quad \Rightarrow \quad m \leq VM(f) \leq M;]

sendo [;f;] contínua, existe [;c \in [a,b];] tal que [;VM(f) = f(c);].

terça-feira

Editorial Fevereiro/2013

Prezados leitores e admiradores do blog. 

Venho comunicar a todos que o blog após três anos, está um problema técnico de não renderizar as equações matemáticas e por isso, todos os posts estão "indecifráveis". Tais posts foi escrito na linguagem tex e usando o complemento Graeseymonkey que apesar de instalado, está com mal funcionamento.

Adotei este sistema pela sua praticidade há mais de três anos e neste período, foram quase 700 posts, sendo que mais de 90% deles possuem alguma fórmula ou expressão matemática. Já descobri duas outras maneiras distintas de colocar as equações no blog, mas terei que alterar manualmente todas as equações, algo completamente inviável.

Peço a paciência e atenção de todos durante este período turbulento. Toda sugestão será bem-vinda.

Atenciosamente, 

Prof. Paulo Sérgio C. Lino
Articulador do blog

sexta-feira

Problemas dos Fatos Matemáticos (Parte 22)

65) Dada a expressão 
onde   são números reais arbitrários, mostre que .

66) Ache todas as soluções reais do sistema de equações
67) Sejam   e números reais não-negativos tal que . Prove que .

68) Considere três jarras com capacidade para e litros. A jarra de litros está cheia de água. Você é capaz de medir exatamente litros? 

Observação: Você não possui outros recipientes para trabalhar e os recipientes não estão marcados, indicando as frações. Você pode despejar a água de um recipiente em outro quantas vezes quiser.

Observação: A novidade dos Problemas dos Fatos Matemáticos neste ano é o número questões que passa de três para quatro em cada mês. 

Vejamos agora, a solução dos problemas dos Fatos Matemáticos (Parte 21).

61) Prove que
 
se é um inteiro positivo. 

Resolução: Pelo binômio de Newton, 
 
 
de modo que 
 

62) Na figura abaixo, e . Sendo , prove que é o ponto médio de
Resolução: Seja um ponto sobre o prolongamento de de modo que , conforme a figura abaixo. 
 
Afirmação 1:  
De fato,
 

 
Assim,
Analogamente,
Portanto, donde segue o resultado. 

Afirmação 2:
De fato, sendo , então e (opostos pelo vértice). Assim, 
 
ou seja, é ponto médio de

63) Prove que existe exatamente uma única terna de números no qual os três números são primos. 
 

Resolução: Se é par, então, então e também são. Mas apenas o é um primo par. Assim, deve ser ímpar. Nesse caso, e também são ímpares. 

Afirmação: , ou é divisível por
De fato, se não é divisível por , então ou , sendo natural. Se , então e se , então . Analogamente, se não é divisível por , então ou . Ambos os casos, ou .

A única possibilidade de um número ser divisível por e primo é que ele seja o próprio . Assim, e . Portanto, a terna procurada é

Observe que qualquer outra terna da forma com n ímpar distinto de deve conter pela afirmação acima, um número que é múltiplo de . Logo, a terna é única.

64) Mostre que 
Resolução: Seja . Assim, 

Logo, 
 
O leitor Sebá enviou a solução do Problema 63.

Participe enviando as soluções dos problemas 65), 66), 67) e 68) no formato doc ou pdf para linnux2001@gmail.com. O prazo de entrega para enviar as soluções destes problemas encerra no dia 10/03/2013.

Gostará de ler também: