Koło matematyczne I LO w Białymstoku

 
Zadania PDF.

Źródło zadań w texu.

%        File: zad.tex
%     Created: Mon Mar 18 11:00 PM 2013 C
% Last Change: Mon Mar 18 11:00 PM 2013 C
\documentclass[10pt, a4paper]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[textwidth=16cm, textheight=26cm]{geometry}
 
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{polski}
\usepackage{graphicx}
\usepackage{enumitem}
\setenumerate{itemsep=2pt,topsep=2pt,parsep=0pt,partopsep=0pt}
\usepackage[pdfborder={0 0 0}]{hyperref}
%\usepackage{MnSymbol}
% ----------------------------------------------------------------
\vfuzz4pt % Don't report over-full v-boxes if over-edge is small
\hfuzz4pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Twierdzenie}
\newtheorem{cor}[thm]{Wniosek}
\newtheorem{lem}[thm]{Lemat}
\newtheorem{defn}[thm]{Definicja}
\newtheorem{tozs}[thm]{Tożsamość}
\newtheorem{hyp}[thm]{Hipoteza}
 
\newcommand{\HRule}{\rule{\linewidth}{0.2mm}}
\renewcommand{\section}[1]{
%\vspace*{-1.5cm}
\stepcounter{section}%
\begin{center}%
    \begin{minipage}{2.5cm}
        \includegraphics[origin=c,width=2.5cm]{\headpicture}
    \end{minipage}\begin{minipage}{\sectionwidth}
        \begin{center}
            {\Huge \bfseries \center #1}
 
            \vskip 1mm
            \small \normalfont \sc
            \author{}\\
            \date{}
        \end{center}
    \end{minipage}
\end{center}
\HRule
}
 
\newenvironment{sol}[1][Rozwiązanie. ]{
\vskip 3mm
\noindent\emph{#1}
 
}
{
 
}
 
\newcounter{problem}
\newenvironment{problem}[1][]{
\stepcounter{problem}
\vskip 3mm
\noindent{\textsc{{\bfseries Zadanie \theproblem{}} #1}}\\}
{
 
}
 
\pagestyle{empty}
 
\def\abs #1{\left\vert #1\right\vert}
 
\renewcommand{\angle}{\sphericalangle}
\renewcommand{\vec}[1]{\overrightarrow{#1}}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\dots}{\ldots}
 
 
\def\sectionwidth{7cm}
\def\headpicture{graf.png}
\def\author{kółko I~LO Białystok}
\def\date{19 marca 2013}
\begin{document}
\section{Grafowie\\\normalsize\emph{Graf} jest to dostojnik w~państwie krzyżackim.
Graf jest \emph{skończony}, jeżeli zginął pod Grunwaldem.
{\tiny[WWW]}}
 
\vspace{0.5cm}
 
Graf = wierzchołki $V$ i~krawędzie $E$ łączące je. Krawędzie mogą być
dwukierunkowe (domyślnie)
lub jednokierunkowe (wtedy graf nazywamy \emph{skierowanym}).
 
Trochę oznaczeń. \emph{Scieżką} nazywamy sam\dywiz wiesz\dywiz jaki ciąg
krawędzi. Graf nazywamy \emph{prostym} jeżeli każde dwa wierzchołki
łączy co najwyżej jedna krawędź i~żadna krawędź nie łączy wierzchołka ze sobą. Graf nazywamy \emph{spójnym} jeżeli każde dwa
wierzchołki łączy (co najmniej jedna) ścieżka. \emph{Cyklem} nazywamy ścieżkę
zaczynającą się i~kończącą w~tym samym wierzchołku.
 
\emph{Cyklem Hamiltona} nazywamy cykl przechodzący przez każdy
\emph{wierzchołek} grafu dokładnie raz (pomijając początkowy). \emph{Cyklem
Eulera} nazywamy cykl przechodzący przez każdą krawędź grafu dokładnie raz.
 
\emph{Stopniem} wierzchołka $v$ grafu nieskierowanego nazywamy liczbę
krawędzi, których końcem jest $v$.
 
\begin{problem}[Drzewa]
    Graf prosty i~spójny ma mniej krawędzi niż wierzchołków. O~ile mniej jest
    krawędzi? Czy graf ten może zawierać cykl?
\end{problem}
 
\begin{problem}
    Udowodnij, że w~kraju, w~którym każde miasto jest połączone z~każdym innym
    drogą jednokierunkową, istnieje miasto, z~którego da się pojechać do
    każdego innego.
\end{problem}
 
\begin{problem}
    Na Inflantach jest $n$ miast, niektóre z~nich łączą jednokierunkowe drogi
    przy czym z~każdego z~miast wychodzi tyle dróg, ile do niego wchodzi.
    Jednym z~miast jest stolica, z~której można dojechać do
    każdego miasta. Uzasadnij, że z~każdego miasta można dojechać do każdego
    innego.
\end{problem}
 
\begin{problem}
    Uczniowie z~2b rozwalili model sześcianu~--- pozostało tylko 7
    wierzchołków ze wszystkimi krawędziami. Na pociechę powiedz im, czy tak
    powstały graf ma cykl Hamiltona (istnienie cyklu ukoiłoby p. Pawłowską).
\end{problem}
 
\begin{problem}
    Ile wynosi suma stopni wierzchołków grafu nieskierowanego? Wywnioskuj
    z~odpowiedzi, że liczba wierzchołków stopnia nieparzystego jest parzysta.
\end{problem}
 
\begin{problem}
    Uzasadnij, że spójny (nieskierowany) graf ma cykl Eulera wtedy i~tylko
    wtedy, gdy stopień każdego z~wierzchołków jest parzysty.
\end{problem}
 
\begin{problem}
    Graf prosty, niespójny $G$ ma $n$ wierzchołków. Ile co najwyżej może on
    mieć krawędzi?
\end{problem}
 
\begin{problem}[$\star$ Twierdzenie Orego]
    Graf prosty $G$ ma $n\geq 3$ wierzchołków. Suma stopni dowolnych
    dwóch z~jego wierzchołków wynosi co najmniej $n$. Uzasadnij, że $G$ ma
    cykl Hamiltona.
 
    \emph{Wskazówka: Możesz wybrać ``największy graf'' który nie spełnia tezy
    tzn. taki, że po dołożeniu dowolnej krawędzi graf już będzie miał cykl.
    Ten cykl trzeba podrasować, żeby pasował i~do mniejszego.}
\end{problem}
 
\begin{problem}
    Na uczcie zwycięstwa zebrało się $2n$ rycerzy polskich. Wiadomo, że każdy
    z~nich kłóci się o~chwałę z~co najwyżej $n-1$ z~pozostałych rycerzy.
    Uzasadnij, że Jagiełło może rozsadzić rycerzy przy okrągłym stole tak, by nikt nie kłócił się
    z~sąsiadem.
\end{problem}
 
\vspace{0.5cm}
\emph{Zadania pochodzą ze Staszica, PB itd., zaś grafowie spod Malborka.}
 
\end{document}