41 lines
1.5 KiB
TeX
41 lines
1.5 KiB
TeX
\documentclass[10pt]{article}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage{amsmath,amsthm,amssymb}
|
|
\usepackage{fullpage}
|
|
\usepackage{url}
|
|
\pagenumbering{gobble}
|
|
\usepackage{hyperref}
|
|
|
|
\title{ Tutorial: Metro}
|
|
\author{OBI 2015}
|
|
\date{}
|
|
\begin{document}
|
|
\maketitle
|
|
O grafo do sistema tem uma propriedade importante: a estação central é a única
|
|
estação com grau pelo menos $5$, pois dela saem todas as linhas radiais. As
|
|
outras estações pertencem a caminhos radiais ou à linha circular. Mesmo uma
|
|
estação onde uma radial encontra o círculo tem grau no máximo $4$.
|
|
|
|
Primeiro encontramos essa estação central analisando os graus dos vértices.
|
|
Depois removemos a central do grafo. O que resta é a linha circular com alguns
|
|
caminhos pendurados nela, correspondentes aos trechos radiais antes ou depois do
|
|
círculo.
|
|
|
|
Para isolar somente a linha circular, fazemos uma poda de folhas:
|
|
\begin{enumerate}
|
|
\item calcule o grau de cada vértice desconsiderando a estação central;
|
|
\item coloque em uma fila todos os vértices de grau $0$ ou $1$;
|
|
\item enquanto a fila não estiver vazia, remova o vértice da frente e reduza
|
|
o grau de seus vizinhos ainda não removidos;
|
|
\item quando algum vizinho passar a ter grau $1$, coloque-o na fila.
|
|
\end{enumerate}
|
|
|
|
Esse processo remove todos os caminhos que estão pendurados no ciclo. Os
|
|
vértices que não foram removidos ao final são exatamente as estações da linha
|
|
circular, então basta contá-los.
|
|
|
|
\textbf{Complexidade de tempo:} $O(N + M)$.
|
|
|
|
\textbf{Complexidade de espaço:} $O(N + M)$.
|
|
\end{document}
|