二分图 and 网络流

📅 Last Updated: 2020-10-04
📊 Word Count: 503
⏱️ Estimated Reading Time: 3 minutes
📄 PDF 📝 Source

一些简单的关于图论的定义和胡扯…

总览

二分图最大匹配

  • O(nm)O(n m)
  • Dinic: O(m(n))O(m \sqrt(n))

二分图最大带权匹配

  • KM算法 O(N3)O(N^3)

定义

  • 最大独立集：在图里选最多的点，使得不存在两个选了的点之间有边。
  • 最小点覆盖：在图里选最少的点，使得每个边连接的两个点至少一个点被选。
  • 最长反链：点集 G 中一个极大的子集 W ， 使得 W 中的点互不可到达。
  • 传递闭包：定义有向图 GG 的传递闭包为 A[i, j]=[点 i 和 点 j 有通路]\text{A[i, j]} = \text{[点 i 和 点 j 有通路]}

定理

  • 最长反链=最小链覆盖\text{最长反链} = \text{最小链覆盖} （dilworth 定理）
  • 二分图最小点覆盖=最大匹配\text{二分图最小点覆盖} = \text{最大匹配}
  • 最小点覆盖+最大独立集=点数\text{最小点覆盖} + \text{最大独立集} = \text{点数},最小覆盖集 与 最大独立集 互为补集, 其并集为点集
  • Hall定理： 设一个二分图的左右部分分别为 X、Y, 且 |X| = |Y|
  • 矩阵树定理证明：有向图矩阵树定理的一个简单组合证明

小问题

  • 求 DAG 最小链覆盖（最长反链）：传递闭包 + 拆点二分图匹配

栗题

4.2（LOJ）

给出一个保证左部满匹配的二分图，保证左部每个点的度数不超过2，边有边权。 支持： - 修改边权 - 查询最大带权匹配 (强制保证任意时刻左侧满匹配)

对左侧点分类： - 度数为 1 ：这条边必须成为匹配边，可直接删除这个点和对应的右边点 - 度数为 2 ：左侧点 u 可直接删掉，在右侧对应的两个点之间直接连两条有向边，给这条边定向，只想哪个点就相当与选哪个点与点 u 相连的边。 - 不难发现这样形成的一张图应该是，若干个 树 和 基环树 组成的森林。根据查询给边定向，其中要求一个点入度数最多为一。树仅需选择一个边定向，在同一个树上的其他边都能被强制定向。对于基环树，环上边需要决定是顺时针还是逆时针，环外的边要指出环

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 962b12d5a7867279220e44b5cef26d039ed8496efbe5a4c6e0727153796a5e2e
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「学习总结」二分图-and-网络流.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「学习总结」二分图-and-网络流.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../8b2da43ef7.pdf.md', '-o', 'cache/8b2da43ef7.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawInline (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={二分图 and 网络流},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{二分图 and 网络流}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-10-04 14:15:07}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  一些简单的关于图论的定义和胡扯…
  
  \subsection{总览}\label{ux603bux89c8}
  
  \subsubsection{二分图最大匹配}\label{ux4e8cux5206ux56feux6700ux5927ux5339ux914d}
  
  \begin{itemize}
  \tightlist
  \item
    \(O(n m)\)
  \item
    Dinic: \(O(m \sqrt(n))\)
  \end{itemize}
  
  \subsubsection{二分图最大带权匹配}\label{ux4e8cux5206ux56feux6700ux5927ux5e26ux6743ux5339ux914d}
  
  \begin{itemize}
  \tightlist
  \item
    KM算法 \(O(N^3)\)
  \end{itemize}
  
  \subsubsection{定义}\label{ux5b9aux4e49}
  
  \begin{itemize}
  \tightlist
  \item
    最大独立集：在图里选最多的点，使得不存在两个选了的点之间有边。
  \item
    最小点覆盖：在图里选最少的点，使得每个边连接的两个点至少一个点被选。
  \item
    最长反链：点集 G 中一个极大的子集 W ， 使得 W 中的点互不可到达。
  \item
    传递闭包：定义有向图 \(G\) 的传递闭包为
    \(\text{A[i, j]} = \text{[点 i 和 点 j 有通路]}\)
  \end{itemize}
  
  \subsubsection{定理}\label{ux5b9aux7406}
  
  \begin{itemize}
  \tightlist
  \item
    \(\text{最长反链} = \text{最小链覆盖}\) （dilworth 定理）
  \item
    \(\text{二分图最小点覆盖} = \text{最大匹配}\)
  \item
    \(\text{最小点覆盖} + \text{最大独立集} = \text{点数}\),\texttt{最小覆盖集}
    与 \texttt{最大独立集} 互为\texttt{补集}, 其\texttt{并集}为点集
  \item
    Hall定理： 设一个二分图的左右部分分别为 X、Y, 且 \textbar X\textbar{}
    = \textbar Y\textbar{}
  \item
    矩阵树定理证明：\href{https://loj.ac/article/2458}{有向图矩阵树定理的一个简单组合证明}
  \end{itemize}
  
  \subsubsection{小问题}\label{ux5c0fux95eeux9898}
  
  \begin{itemize}
  \tightlist
  \item
    求 DAG 最小链覆盖（最长反链）：传递闭包 + 拆点二分图匹配
  \end{itemize}
  
  \subsection{栗题}\label{ux6817ux9898}
  
  \subsubsection{4.2（LOJ）}\label{loj}
  
  给出一个保证左部满匹配的二分图，保证左部每个点的度数不超过2，边有边权。
  支持： - 修改边权 - 查询最大带权匹配 (强制保证任意时刻左侧满匹配)
  
  对左侧点分类： - 度数为 1
  ：这条边必须成为匹配边，可直接删除这个点和对应的右边点 - 度数为 2
  ：左侧点 u
  可直接删掉，在右侧对应的两个点之间直接连两条有向边，给这条边定向，只想哪个点就相当与选哪个点与点
  u 相连的边。 - 不难发现这样形成的一张图应该是，若干个 树 和 基环树
  组成的森林。根据查询给边定向，其中要求一个点入度数最多为一。树仅需选择一个边定向，在同一个树上的其他边都能被强制定向。对于基环树，环上边需要决定是顺时针还是逆时针，环外的边要指出环
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 78.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1] [2] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (2 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 78.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1] [2] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (2 pages).
  Transcript written on .../input.log.