Componentes conectados em Grafos

Em um grafo não-direcionado G, dois vértices u e v são ditos conectados se G contém um caminho de u para v. Senão, eles são chamados de desconectados.  Um grafo orientado (ou direcionado) é chamado de fracamente conectado se a substituição de todas as suas arestas direcionadas por arestas não direcionadas produz um grafo (não-direcionado) conectado. Ele é chamado de conectado se possui um caminho direcionado de u para v ou um caminho direcionado de v para u para cada par de vértices u, v. Ele é fortemente conexo se contém um caminho direto de u para v e um caminho direto v para u para cada par de vértices u, v. Um vértice de corte de um grafo conexo G é um conjunto de vértices que quando removidos torna G desconexo.

Um grafo não direcionado é conectado se cada par de vértices está conectado por um caminho. Os componentes conectados são as porções conectadas de um grafo. Um grafo não direcionado é conectado se ele tem exatamente um componente conectado.
Os componentes fortemente conexos são os subgrafos maximais fortemente conectados.

Os componentes fortemente conectados de um grafo direcionado são conjuntos de vértices sob a relação “são mutuamente alcançáveis”.

Por exemplo {0, 1, 2, 3}, {4} e {5} são os componentes fortemente conectados, {4, 5} não o é, pois o vértice 5 não é alcançável a partir do vértice 4.

O Algoritmo para achar estes componentes é:

1. Aplicar a busca em profundidade no grafo G para obter os tempos de término t[u] para cada vértice u. 
2. Obter o grafo G', que é o grafo transposto, isto é, são os mesmos vértices mas as arestas são invertidas. Assim existe uma arestas (u,v) em G' se existe uma aresta (v,u) em G. 
3. Aplicar a busca em profundidade no grafo G' realizando a busca a partir do vértice de maior t[u] obtido na linha 1.
4. Se a busca em profundidade não alcançar todos os vértices, inicie uma nova busca em profundidade a partir do vértice de maior t[u] dentre os vértices restantes.
5. Retornar os vértices de cada árvore da floresta obtida na busca em profundidade na linha 3 como um componente fortemente conectado separado.

Ativando Wi-Fi no Raspberry PI 2/3 usando a linha de comando

Para rodar o wifi (contando que o driver da placa wifi tenha sido reconhecida e carregada), você precisa do wpa_supplicant. Ele pode ser instalado usando

sudo apt-get instal wpa_supplicant.


Você pode tentar seguir o guia do site do Raspberry Pi. No meu caso o guia não funcionou pois ele considera a alteração no arquivo /etc/network/interfaces, mas no meu Pi  esta alteração não tem efeito.

1) criar o arquivo de configuração do wpa_supplicant
Você terá que editar (criar) o arquivo /etc/wpa_supplicant/wpa_supplicant.conf. Ele deverá ter no mínimo as linhas abaixo.

country=BR
ctrl_interface=DIR=/var/run/wpa_supplicant GROUP=netdev
update_config=1
network={
    ssid="SSID do seu AP"
    psk="senha do seu AP"
}

Edite as linhas SSID e psk para conter o nome da sua rede sem fio (ESSID) e a senha da rede.

2) criar um script para rodar o wpa_supplicant. No meu caso eu coloquei em /etc/init.d/wpa_supplicant. Veja no script que está indicado a interface wlan0 onde será feita a conexão. No caso do seu Pi, você tem que configurar para o nome correto da interface.

#! /bin/sh

### BEGIN INIT INFO

# Provides: wpa_supplicant

# Required-Start:    $local_fs $syslog $remote_fs dbus

# Required-Stop:     $local_fs $syslog $remote_fs

# Default-Start:     2 3 4 5

# Default-Stop:      0 1 6

# Short-Description: Start wpa_supplicant daemon

### END INIT INFO

# este script não estava rodando nos diretorios rcX.d

# ele deveria ficar ativo usando

# update_rc.d wpa_supplicant enable

# contudo apesar de criar os links ele não funcionou

# 

# para ativá-lo eu tive que chamar o script em /etc/rc.local

DAEMON=/sbin/wpa_supplicant

DESC="wpa_supplicant wlan0"

CONF=/etc/wpa_supplicant/wpa_supplicant.conf

test -f $DAEMON || exit 0

# FIXME: any of the sourced files may fail if/with syntax errors

test -f $CONF

case $1 in

  start)

  echo "Starting $DESC"

  $DAEMON -i wlan0 -c $CONF -B

  ;;

  stop)

  echo "Stopping $DESC"

  pkill wpa_supplicant

  ;;

  

  restart|force-reload)

  $0 stop

  sleep 1

  $0 start

  ;;

  

  *)

  echo "Usage: $0 {start|stop|restart}" >&2

  exit 1

  ;;

esac

exit 0

3) alterar o arquivo /etc/rc.local para chamar o script criado no passo (2). No meu caso eu simplesmente inseri a linha abaixo

/etc/init.d/wpa_supplicant start

Não é necessária nenhuma outra configuração. Meu arquivo /etc/network/interfaces possui 3 linhas relacionadas com wlan0, contudo elas não fazem efeito real. Reproduzo abaixo somente para vocês verem o que são.

allow-hotplug wlan0

iface wlan0 inet manual 

    wpa-conf /etc/wpa_supplicant/wpa_supplicant.conf

Bug PCManFM - Não abre o terminal

Se você é como eu e usa bastante o terminal no linux, tem uma característica interessante que é abrir o terminal no diretório corrente dentro do navegador. O Ubuntu é possível adicional ao menu de contexto uma opção "Abrir no terminal". Para isto basta instalar  esta opção ao Nautilus:

sudo apt-get install nautilus-open-terminal

Basta reiniciar o nautilus com (nautilus -q) para que a opção já esteja ativa.

Contudo se você utiliza o LUbuntu, o navegador é o PCManFM. Ele tem está opção no menu de ferramenta que é acionada via teclado usando <F4>. Contudo ela tem um bug.







A instalação padrão não abre diretórios com espaços como no meu exemplo da "Área de Trabalho". Esta opção de menu aciona um script que está no arquivo /usr/bin/lxsession-default-terminal. Dentro deste script vemos que a variável $PWD não está entre aspas. Basta consertar como na imagem abaixo e pronto. O <F4> funciona.